在這篇文章中,我們需要藉助單鍊錶來反轉連結。我們的任務是創建一個能夠反轉給定單鍊錶的函數。例如
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中文網其他相關文章!