首页 > 后端开发 > C++ > 正文

使用C++反转一个链表

WBOY
发布: 2023-08-27 12:09:21
转载
714 人浏览过

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

来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板