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

이 기사에는 이중 연결 목록이 있으며 C++에서 이중 연결 목록을 되돌리는 다양한 방법을 설명합니다. 예를 들어 -

Input : {1, 2, 3, 4}
Output : {4, 3, 2, 1}

일반적으로 한 가지 방법이 떠오르는데, 우리는 일반적인 방법과 비정통적인 방법이라는 두 가지 방법을 사용하겠습니다.

Normal Method

이 방법에서는 목록을 살펴보고 이를 살펴보면서 목록을 반대로 합니다.

예제

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};

void reverse(Node **head_ref) {
   auto temp = (*head_ref) -> next;
   (*head_ref) -> next = (*head_ref) -> prev;
   (*head_ref) -> prev = temp;
   if(temp != NULL) {
      (*head_ref) = (*head_ref) -> prev;
      reverse(head_ref);
   }
   else
      return;
}
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout << "Before\n" ;
   while(node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
   reverse(&head);
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

출력

Before
9 8 4 6
After
6 4 8 9

이 접근 방식에는 O(N)시간 복잡도가 필요하며, 이 복잡도는 더 높은 제약 조건에서 수행될 수 있기 때문에 매우 좋습니다.

비정통적인 방법

이름에서 알 수 있듯이 사용자들이 흔히 생각하는 방법은 아니지만 이 방법도 살펴보겠습니다. 이 접근 방식에서는 스택을 생성하고 거기에 데이터를 계속 밀어넣고 팝업 시 해당 값을 변경합니다.

Example

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout >> "Before\n" ;
   while(node != NULL) {
      cout >> node->data >> " ";
      node = node->next;
   }
   cout >> "\n";
   stack<Node*> s;
   node = head;
   while(node) {
      head = node;
      s.push(node);
      node = node -> next;
   }
   while(!s.empty()) {
      auto x = s.top();
      auto temp = x -> prev;
      x -> prev = x -> next;
      x -> next = temp;
      s.pop();
   }
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

Output

Before
9 8 4 6
After
6 4 8 9

위 코드 설명

이 접근 방식에서는 스택을 사용하고 목록을 순회하면서 스택을 채운 다음 스택에서 항목을 팝하고 해당 값을 변경하여 목록이 그 반대입니다. O(N)은 이 프로그램의 시간 복잡도이며 더 높은 제약 조건에도 적용됩니다.

결론

이 기사에서는 스택을 사용하거나 사용하지 않고 이중 연결 목록을 되돌리는 문제를 해결했습니다. 시간 복잡도는 O(N)입니다. 여기서 N은 목록의 크기입니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 방법(정상 및 비정통)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

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