在本文中,我们需要借助单向链表来反转链接。我们的任务是创建一个能够反转给定单链表的函数。例如
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; } // 打印链表的函数 void reverse() { auto curr = head; // 当前指针 Node* prev = NULL; // 前一个指针 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; } // 打印链表的函数 void reverse() { auto curr = head; // 当前指针 Node* prev = NULL; // 前一个指针 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; } // 打印链表的函数 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; // 当前指针 Node* prev = NULL; // 前一个指针 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++ 程序以及解决此问题的完整方法(Normal 和其他两种方法)。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。我们希望这篇文章对您有所帮助。