反转链表
题目描述
思路
方法一：迭代
这题不难，用链表解决即可。在遍历链表的时候，让当前遍历到的节点的next指针指向上一个节点即可。这个想法的时间复杂度是$O(n)$，其中$n$是链表的长度。只需要遍历一次链表即可。空间复杂度为$O(1)$。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* next = nullptr;
while(cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
方法二：递归
递归的写法更简洁，通过调用函数本身来实现循环。递归的时间复杂度是$O(n)$，其中$n$是链表的长度。需要对链表的每个节点进行反转操作。他的空间复杂度是$O(n)$，其中$n$是链表的长度。空间复杂度主要取决于递归调用的栈空间。
写递归的时候，首先需要明确递归的初始状态和结束条件。每一个递归状态，输入为两个指针pre和cur，输出为一个ListNode*类型的指针。所以可以定义一个新的递归函数ListNode* reverse(ListNode* cur, ListNode* pre)。递归的初始状态，cur为head，pre为nullptr，结束条件为，当前指针cur指向nullptr。因此，递归函数如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
return reverse(head, nullptr);
}
ListNode* reverse(ListNode* cur, ListNode* pre) {
if (cur == nullptr) return pre; // 终止条件
ListNode* res = reverse(cur->next, cur); // 递归后继节点
cur->next = pre; // 做反转操作
return res; // 返回上层递归
}
};
文档信息
- 本文作者：焦逸凡
- 本文链接：https://ailovejinx.github.io/wiki/leetcode206/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）