> 백엔드 개발 > C++ > 본문

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

WBOY
풀어 주다: 2023-08-27 12:09:21
앞으로
715명이 탐색했습니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿