反转链表系列问题
作者：Grey
原文地址：
反转单链表
题目描述见：LeetCode 206. Reverse Linked List
思路如下
对于任何一个节点 cur 来说，记录一个前驱节点 pre (第一个节点的前驱节点是 null )
先用一个临时节点 tmp 记录 cur 的下一个节点，然后设置
cur.next = pre;
pre = cur;
cur = tmp;
以下是示例图
假设原始链表如下
第一个节点的反转流程如下
第二个节点的反转流程如下
最后返回 pre 节点即为反转后的节点。
代码如下
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
时间复杂度\(O(N)\)，空间复杂度\(O(1)\)。
反转链表也可以用递归方法来实现
定义递归函数 ListNode reverse(ListNode cur)，这个递归函数的含义是
反转以 cur 为头的链表，并把反转后的头节点返回。
这个递归函数的 base case 是，只有一个节点的时候，即
if (cur == null || cur.next == null) {
return cur;
}
这种情况下，直接返回当前节点即可。
接下来是普遍情况：
当前来到 cur 节点，c，d，e 已经完成了反转。
此时 cur 需要做如下操作：把 c , d, e 反转后的头节点获取到，假设为 pre ， 在上图中，pre 就是 e 节点，然后 cur 再做如下操作
cur.next.next = cur;
cur.next = null;
其中cur.next = null非常重要，只有这样，才能防止出现环。完整代码如下
class Solution {
public ListNode reverseList(ListNode cur) {
return reverse(cur);
}
// 反转cur为头的链表，并把反转后的头节点返回
public ListNode reverse(ListNode cur) {
if (cur == null || cur.next == null) {
return cur;
}
ListNode pre = reverse(cur.next);
cur.next.next = cur;
cur.next = null;
return pre;
}
}
时间复杂度\(O(N)\)
空间复杂度\(O(N)\)(递归栈占用的空间)
反转双向链表
双向链表和单链表的反转类似，每个节点要多处理一次每个节点的前驱指针，
完整代码如下
public static DoubleNode reverseDoubleList(DoubleNode head) {
if (head == null || head.next == null) {
return head;
}
DoubleNode pre = null;
DoubleNode cur = head;
while (cur != null) {
DoubleNode tmp = cur.next;
cur.next = pre;
cur.last = tmp;
pre = cur;
cur = tmp;
}
return pre;
}
反转单链表一部分
题目描述见：LeetCode 92. Reverse Linked List II
本题核心依然是反转链表，只是增加了一些变量来记录需要反转链表的头位置和结尾位置，不过需要注意的是，本题的链表开始位置是从 1 开始，所以，如果m = 1 && n != 1，说明反转链表后需要返回新的头部，只要m > 1，反转链表一部分以后，返回原先的头即可。
此外，本题的 follow up 提到
Follow up: Could you do it in one pass?
就是遍历一次链表能否解决问题，具体代码如下
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head.next == null || left == right) {
// 只有一个节点，怎么反转都一样
// 只要反转一个节点，反转前后链表还是一样的
return head;
}
if (left == 1) {
// 需要换头
ListNode pre = null;
ListNode end = head;
ListNode cur = head;
int gap = right - left + 1;
while (gap != 0) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
gap--;
}
end.next = cur;
return pre;
} else {
ListNode pre = null;
for (int i = 1; i < left; i++) {
pre = pre == null ? head : pre.next;
}
ListNode end = pre;
ListNode cur = pre == null ? head : pre.next;
ListNode last = cur;
int gap = right - left + 1;
while (gap != 0) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
gap--;
}
if (end != null) end.next = pre;
if (last != null) last.next = cur;
// 不需要换头，返回原先的头节点
return head;
}
}
}