倒转链表：2个简单实现

宁立 · 发布于 2023-8-21 12:24:26

大家好，今天和大家分享的是反转链表的两种方法，第一种是用泛型编程里面的STL，第二种是利用多个指针停止操作，小孩子才做选择，建议两个都学。我们往下看：

一.使用vector容器

ps：该方法对内存的需求较高，这是个缺点，可以直接使用STL容器自带的reverse停止反转(将vector容器内的结点停止反转，然后再用for循环将他串联起来)，实现起来相对容易，思路不太复杂。
请看以下代码：

typedef struct Node
{
int val;
struct Node*next;
}ListNode;
class traverse {
public:
ListNode* ReverseList(ListNode* pHead) {
if (!pHead) return nullptr;
vector<ListNode*> v;
while (pHead) {
v.push_back(pHead);
pHead = pHead->next;
}
reverse(v.begin(), v.end()); // 反转vector，也可以逆向遍历
ListNode *head = v[0];
ListNode *cur = head;
for (int i=1; i<v.size(); ++i) { // 构造链表
cur->next = v[i]; // 当前节点的下一个指针指向下一个节点
cur = cur->next; // 当前节点后移
}
cur->next = nullptr; // 切记最后一个节点的下一个指针指向nullptr
return head;
}
};

复制代码

此方法的复杂度：
时间复杂度：O(n)
空间复杂度：O(n), 用了一个vector来存单链表

二.调整指针法

ps：此方法更加妥当，能得到更多人的喜欢，很好的利用几个指针的指向反转一个链表。
初始化：3个指针
1）pre指针指向已经反转好的链表的最后一个节点，最开端没有反转，所以指向nullptr
2）cur指针指向待反转链表的第一个节点，最开端第一个节点待反转，所以指向head
3）nex指针指向待反转链表的第二个节点，目的是保管链表，因为cur改变指向后，后面的链表则失效了，所以需要保管
接下来，循环执行以下三个操作
1）nex = cur->next, 保管作用
2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点
3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点
循环条件，当然是cur != nullptr
循环完毕后，cur当然为nullptr，所以返回pre，即为反转后的头结点
这里以1->2->3->4->5 举例：

代码如下：

class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode *pre = nullptr;
ListNode *cur = pHead;
ListNode *nex = nullptr; // 这里可以指向nullptr，循环里面要重新指向
while (cur) {
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
};

复制代码

此方法复杂度：
时间复杂度：O(n), 遍历一次链表
空间复杂度：O(1)
总结：要从易懂的角度来看，第一种不失是好的，使用STL，我如今才大一，我听说一些面试是不允许使用STL这一内容解体的。第二种方法很妙，复杂度是比较理想的，而且用到了灵魂指针的应用。建议大家多琢磨一下第二种方法。
到此这篇关于C++实现反转链表的两种方法的文章就介绍到这了,更多相关C++ 反转链表内容请搜索网站以前的文章或继续阅读下面的相关文章希望大家以后多多支持网站！