연결리스트를 역방향으로 변환하는 C 프로그램

이 질문에는 연결 목록이 제공됩니다. 우리의 임무는 연결된 목록을 뒤집는 프로그램을 만드는 것입니다.

이 프로그램은 주어진 연결 리스트를 반전하고 반전된 연결 리스트를 반환합니다.

연결된 목록은 항목을 포함하는 연결된 시퀀스입니다. 각 링크에는 다른 링크에 대한 연결이 포함되어 있습니다.

Example

9 -> 32 -> 65 -> 10 -> 85 -> NULL

Reverse linked list는 연결리스트의 링크를 반대로 바꾸어 연결리스트를 만드는 것입니다. 연결 리스트의 헤드 노드는 연결 리스트의 마지막 노드가 되고, 마지막 노드는 헤드 노드가 됩니다.

Example

위 연결리스트로 구성된 역연결리스트 −

85 -> 10 -> 65 -> 32 -> 9 -> NULL

주어진 연결리스트를 역전시키기 위해 포인터 3개를 추가로 사용하여 처리하겠습니다. 이러한 포인터는 이전, 이후 및 현재입니다.

처음에는 이전과 이후를 모두 NULL로 설정하고 현재를 연결 목록의 선두로 설정합니다.

이후 초기 연결리스트의 NULL에 도달할 때까지 반복합니다. 그런 다음 다음을 수행하세요.

after = current ->
next current ->
next = previous
previous = current
current = after

이제 연결 목록을 역전시키는 프로그램을 만들어 보겠습니다. 이 프로그램을 작성하는 방법에는 두 가지가 있습니다. 하나는 반복적이고 다른 하나는 재귀적입니다.

연결된 목록을 뒤집는 프로그램(꼬리 재귀적 방법)

예제

Demonstration

#include <stdio.h>
struct Node {
   int data;
   struct Node* next;
};
Node* insertNode(int key) {
   Node* temp = new Node;
   temp->data = key;
   temp->next = NULL;
   return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
   if (!current->next) {
      *head = current;
      current->next = previous;
      return;
   }
   Node* next = current->next;
   current->next = previous;
   tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
   if (!head)
      return;
   tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
   while (head != NULL) {
      printf("%d ", head->data);
      head = head->next;
   }
   printf("</p><p>");
}
int main(){
   Node* head1 = insertNode(9);
   head1->next = insertNode(32);
   head1->next->next = insertNode(65);
   head1->next->next->next = insertNode(10);
   head1->next->next->next->next = insertNode(85);
   printf("Linked list : \t");
   printLinkedList(head1);
   tailRecReveseLL(&head1);
   printf("Reversed linked list : \t");
   printLinkedList(head1);
   return 0;
}

Output

Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9

연결된 목록을 뒤집는 프로그램(반복 방법)

Example

실시간 시연

#include <stdio.h>
struct Node {
   int data;
   struct Node* next;
   Node(int data){
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList(){
      head = NULL;
   }
   void interReverseLL(){
      Node* current = head;
      Node *prev = NULL, *after = NULL;
      while (current != NULL) {
         after = current->next;
         current->next = prev;
         prev = current;
         current = after;
      }
      head = prev;
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         printf("%d ", temp-> data);
         temp = temp->next;
      }
      printf("</p><p>");
   }
   void push(int data){
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList linkedlist;
   linkedlist.push(85);
   linkedlist.push(10);
   linkedlist.push(65);
   linkedlist.push(32);
   linkedlist.push(9);
   printf("Linked List : \t");
   linkedlist.print();
   linkedlist.interReverseLL();
   printf("Reverse Linked List : \t");
   linkedlist.print();
   return 0;
}

출력

Linked List : 9 32 65 10 85
Reverse Linked List : 85 10 65 32 9

위 내용은 연결리스트를 역방향으로 변환하는 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!