이 글에서는 단일 연결 리스트의 도움으로 링크를 반전시켜야 합니다. 우리의 임무는 주어진 단일 연결 리스트를 되돌릴 수 있는 함수를 만드는 것입니다. 예를 들어
Input: Following Linked list : 1->2->3->4->NULL Output: After processing of our function: 4->3->2->1->NULL
연결된 목록을 되돌리는 방법에는 여러 가지가 있습니다. 일반적으로 우리는 연결리스트를 순회하면서 이를 역순으로 바꾸는 간단한 방법을 생각합니다.
이 방법에서는 연결된 목록을 순회하고 순회 중에 역방향을 시도합니다.
#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(); }
85 15 4 20 20 4 15 85
이 접근 방식에서는 목록을 반복하고 반복 중에 이를 반대로 합니다. 시간 복잡도가 O(N)(여기서 N은 목록의 크기)이므로 이는 좋은 접근 방식입니다.
이제 실험을 해보고 스택을 사용하여 목록을 반전해 보겠습니다.
스택을 사용하여 이 프로그램의 모든 노드를 저장하고 스택을 순회하여 반전시킵니다.
#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(); }
85 15 4 20 20 4 15 85
이 방법에서는 목록을 순회하면서 목록 노드를 스택에 저장한 다음 스택을 사용하여 이를 팝하고 목록의 목적을 뒤집습니다. 방법 시간 복잡도도 O(N)입니다. 여기서 N은 목록의 크기입니다. 이전과 마찬가지로 스택을 사용하였으니 재귀적 방법도 사용할 수 있는데, 재귀에서도 스택을 사용하므로 이제 재귀적 방법을 사용하겠습니다.
이 방법에서는 이전과 동일한 프로세스를 수행하지만 재귀 호출을 사용합니다.
#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(); }
85 15 4 20 20 4 15 85
이 접근 방식에서는 이전과 동일하지만 재귀 호출을 사용하므로 이 접근 방식의 시간 복잡도도 O(N)입니다. 여기서 N은 목록의 크기입니다.
이 글에서는 단일 연결 리스트의 역전 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위해 C++ 프로그램과 완전한 방법(일반 방법과 다른 두 가지 방법)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.
위 내용은 C++를 사용하여 연결 목록 뒤집기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!