使用C++反转一个链表

在这篇文章中，我们需要借助单链表来反转链接。我们的任务是创建一个能够反转给定单链表的函数。例如

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中文网其他相关文章！