이 기사에서는 단일 연결 목록을 사용하여 링크를 역전시켜야 합니다. 우리의 임무는 주어진 단일 연결 리스트를 뒤집을 수 있는 함수를 만드는 것입니다. 예를 들어
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 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.