反转链表

反转链表是双指针技巧在链表上的典型例题之一。

反转链表Ⅰ

206. 反转链表

反转链表的方式有很多，这里记录一种原地修改节点引用的方式：让每个节点的 next 指向其前驱节点，相当于让节点的引用“掉头”。

例如：

▼
text
复制代码
1 → 2 → 3 → null

原地掉头之后：

▼
text
复制代码
null ← 1 ← 2 ← 3

这样便巧妙地反转了链表。

对于每个节点 p，我们让 p.next 指向其前驱节点。为了避免修改 p.next 后丢失原来的后继节点，我们需要在修改 p.next 之前记录其原来的值，记为 next。

通过上述分析，我们需要三个指针配合工作：

• p：当前节点
• pre：p 的前驱节点。头节点没有前驱节点，因此 pre 初始为 null。
• next：在修改 p.next 之前记录 p 原来的下一个节点。修改完成后，通过 next 找到下一个待处理的节点。

基于上述分析，不难写出如下代码：

▼
java
复制代码
public ListNode reverseList(ListNode head) {
    ListNode pre = null, p = head, next;
    while (p != null) {
        next = p.next;
        p.next = pre;
        pre = p;
        p = next;
    }
    return pre;
}

上述操作只需遍历一遍链表，因此时间复杂度为 $O(n)$。

反转链表 Ⅱ

92. 反转链表 II

现在题目要求我们给链表中指定区间内的节点进行反转操作。

首先，由于反转区间可能包含头节点，反转后链表的头节点可能发生变化。因此我们使用 dummyNode，方便统一处理。

之前我们已经掌握了反转整个链表的方法。那我们能不能复用之前的思路呢？

在上一题中，我们是从头节点开始，一直反转到链表末尾，而这道题则是将反转范围限制在了 [left, right] 区间内。

如果我们能够精确控制遍历的范围，只反转 [left, right] 区间内的节点，是不是就可以解决这道题呢？

在正式开始之前，我们可以先考虑一个边界情况：若反转区间只有一个节点，我们还需要进行反转吗？

显然不需要，对于这种情况直接返回原链表即可。

现在开始正式解决问题吧！我们以下面这幅图为示例：

待翻转区间为 left = 2，right = 4。

首先，我们需要找到第 left 个节点的前驱节点。从 dummyNode 开始向后走 left - 1 步，即可定位到第 left 个节点的前驱节点，记为 before：

然后，我们按照反转链表Ⅰ中的思路，反转 [left, right] 区间内的节点。反转结束后的情况如下图：

由图可知，有以下几个关键点：

• before 后面的节点是反转后的区间尾节点。
• pre 指向反转后的区间头节点。
• p 和 next 都指向原来第 right 个节点的后继节点。

基于以上信息，我们再把链表缝合起来就大功告成了：

最后规整一下：

这样我们便完成了对指定区间内的链表进行局部反转的操作！

基于上述分析，不难写出如下代码：

▼
java
复制代码
public ListNode reverseBetween(ListNode head, int left, int right) {
    if (right - left + 1 <= 1) {
        return head;
    }
    ListNode dummy = new ListNode(-1, head);
    // 定位第 left 个节点的前驱节点；
    ListNode before = dummy;
    for (int i = 0; i < left - 1; i++) {
        before = before.next;
    }
    // 反转 [left, right] 范围内的节点
    ListNode p = before.next, next = null, pre = null;
    for (int i = left; i <= right; i++) {
        next = p.next;
        p.next = pre;
        pre = p;
        p = next;
    }
    before.next.next = next;
    before.next = pre;
    return dummy.next;
}

上述操作只需遍历一遍链表，因此时间复杂度为 $O(n)$。