0206. 反转链表
https://leetcode-cn.com/problems/reverse-linked-list/
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
- 阿里
- 百度
- 腾讯
- adobe
- amazon
- apple
- bloomberg
- facebook
- microsoft
- snapchat
- twitter
- uber
- yahoo
- yelp
- zenefits
这个就是常规操作了，使用一个变量记录前驱 pre，一个变量记录后继 next，不断更新
current.next = pre 就好了。链表的题目 90% 的 bug 都出现在：
- 1.头尾节点的处理
- 2.指针循环引用导致死循环
因此大家对这两个问题要保持 100% 的警惕。
- 链表的基本操作（交换）
- 虚拟节点 dummy 简化操作
- 注意更新 current 和 pre 的位置， 否则有可能出现溢出
语言支持：JS, C++, Python,Java
JavaScript Code：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
if (!head || !head.next) return head;
let cur = head;
let pre = null;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
};
C++ Code：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
Python Code:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head: return None
prev = None
cur = head
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev
Java Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
通过单链表的定义可以得知，单链表也是递归结构，因此，也可以使用递归的方式来进行 reverse 操作。
由于单链表是线性的，使用递归方式将导致栈的使用也是线性的，当链表长度达到一定程度时，递归会导致爆栈，因此，现实中并不推荐使用递归方式来操作链表。
- 1.除第一个节点外，递归将链表 reverse
- 2.将第一个节点添加到已 reverse 的链表之后
这里需要注意的是，每次需要保存已经 reverse 的链表的头节点和尾节点
C++实现
// 普通递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tail = nullptr;
return reverseRecursive(head, tail);
}
ListNode* reverseRecursive(ListNode *head, ListNode *&tail) {
if (head == nullptr) {
tail = nullptr;
return head;
}
if (head->next == nullptr) {
tail = head;
return head;
}
auto h = reverseRecursive(head->next, tail);
if (tail != nullptr) {
tail->next = head;
tail = head;
head->next = nullptr;
}
return h;
}
};
// （类似）尾递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return head;
return reverseRecursive(nullptr, head, head->next);
}
ListNode* reverseRecursive(ListNode *prev, ListNode *head, ListNode *next)
{
if (next == nullptr) return head;
auto n = next->next;
next->next = head;
head->next = prev;
return reverseRecursive(head, next, n);
}
};
JavaScript 实现
var reverseList = function (head) {
// 递归结束条件
if (head === null || head.next === null) {
return head;
}
// 递归反转 子链表
let newReverseList = reverseList(head.next);
// 获取原来链表的第 2 个节点 newReverseListTail
let newReverseListTail = head.next;
// 调整原来头结点和第 2 个节点的指向
newReverseListTail.next = head;
head.next = null;
// 将调整后的链表返回
return newReverseList;
};
Python 实现
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
ans = self.reverseList(head.next)
head.next.next = head
head.next = None
return ans
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 8mo ago