C++를 사용하여 연결 목록 뒤집기

이 글에서는 단일 연결 리스트의 도움으로 링크를 반전시켜야 합니다. 우리의 임무는 주어진 단일 연결 리스트를 되돌릴 수 있는 함수를 만드는 것입니다. 예를 들어

Input:
Following Linked list :
1->2->3->4->NULL

Output:
After processing of our function:
4->3->2->1->NULL

해결 방법을 찾는 방법

연결된 목록을 되돌리는 방법에는 여러 가지가 있습니다. 일반적으로 우리는 연결리스트를 순회하면서 이를 역순으로 바꾸는 간단한 방법을 생각합니다.

쉬운 방법

이 방법에서는 연결된 목록을 순회하고 순회 중에 역방향을 시도합니다.

Example

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList() { head = NULL; }
   // Function to print linked list
   void reverse() {
      auto curr = head; // current pointer
      Node* prev = NULL; // previous pointer
      while(curr) {
         auto temp = curr -> next;
         curr -> next = prev;
         prev = curr;
         head = prev;
         curr = temp;
      }
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

Output

85 15 4 20
20 4 15 85

이 접근 방식에서는 목록을 반복하고 반복 중에 이를 반대로 합니다. 시간 복잡도가 O(N)(여기서 N은 목록의 크기)이므로 이는 좋은 접근 방식입니다.

이제 실험을 해보고 스택을 사용하여 목록을 반전해 보겠습니다.

스택을 이용한 방법

스택을 사용하여 이 프로그램의 모든 노드를 저장하고 스택을 순회하여 반전시킵니다.

Example

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList() { head = NULL; }
   // Function to print linked list
   void reverse() {
      auto curr = head; // current pointer
      Node* prev = NULL; // previous pointer
      stack<Node *> s;
      while(curr) {
         s.push(curr);
         curr = curr -> next;
      }
      prev = s.top();
      head = prev;
      s.pop();
      while(!s.empty()) {
         auto temp = s.top();
         s.pop();
         prev -> next = temp;
         prev = temp;
      }
      prev -> next = NULL;
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

Output

85 15 4 20
20 4 15 85

위 코드 설명

이 방법에서는 목록을 순회하면서 목록 노드를 스택에 저장한 다음 스택을 사용하여 이를 팝하고 목록의 목적을 뒤집습니다. 방법 시간 복잡도도 O(N)입니다. 여기서 N은 목록의 크기입니다. 이전과 마찬가지로 스택을 사용하였으니 재귀적 방법도 사용할 수 있는데, 재귀에서도 스택을 사용하므로 이제 재귀적 방법을 사용하겠습니다.

재귀적 방법

이 방법에서는 이전과 동일한 프로세스를 수행하지만 재귀 호출을 사용합니다.

Example

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
      }
   };
   struct LinkedList {
      Node* head;
      LinkedList() { head = NULL; }
      // Function to print linked list
      void rreverse(Node *curr, Node *prev) {
         if(curr == NULL) {
            // prev -> next = curr;
            head = prev;
            return;
         }
         rreverse(curr -> next, curr);
         curr -> next = prev;
         prev -> next = NULL;
      }

      void reverse() {
         auto curr = head; // current pointer
         Node* prev = NULL; // previous pointer
         rreverse(curr -> next, curr);
      }
      void print() {
         struct Node* temp = head;
         while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

Output

85 15 4 20
20 4 15 85

이 접근 방식에서는 이전과 동일하지만 재귀 호출을 사용하므로 이 접근 방식의 시간 복잡도도 O(N)입니다. 여기서 N은 목록의 크기입니다.

결론

이 글에서는 단일 연결 리스트의 역전 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위해 C++ 프로그램과 완전한 방법(일반 방법과 다른 두 가지 방법)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 연결 목록 뒤집기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!