【算法100天 | 5】图解从easy到hard的链表反转，执行用时超越100%用户（LeetCode 206 ＞ 92 ＞ 25）

1、LeetCode 206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

1）示例

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

2）思路

迭代处理；在遍历链表时，将当前节点的 next 指针改为指向前一个节点。

因为每个节点并不知道它的前一个节点，所以在遍历每一个链表节点之前 都要先存储其前一个节点。在更改节点的next指针之前，需要先将其后一个节点存储下来，用于后面的遍历。

最后返回新的头引用。

3）代码

public static Node reverseLinkedList(Node head) {
    Node cur = null;
    Node next;
    while (head != null) {
        next = head.next;
        head.next = cur;
        cur = head;
        head = next;
    }
    return cur;
}

2、反转双向链表

给你双向链表的头节点 head ，请你反转链表，并返回反转后的链表。

1）思路

思路和反转单向链表类似，同样是迭代处理；唯一的不同是，在迭代时双向链表需要处理prev引用。

2）代码

class DoubleNode {
    public int value;
    public DoubleNode prev;
    public DoubleNode next;

    public DoubleNode(int data) {
        value = data;
    }
}

public static DoubleNode reverseDoubleLinkedList(DoubleNode head) {
    DoubleNode cur = null;
    DoubleNode next;

    while (head != null) {
        next = head.next;
        head.next = cur;
        // 和单向链表相比，仅多一个prev指针的赋值
        head.prev = next;
        cur = head;
        head = next;
    }
    return cur;
}

3、LeetCode 92 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

1）示例

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

2）思路

首先找到要反转的节点，记为：startReverse；其前一个节点（转链表段的前一个节点），记为：preReverse。

从startReverse开始遍历到其后的right - left个节点（endReverse），将这其中每个节点的next指针指向前一个节点，startReverse节点的next指针指向 开始遍历时endReverse的next节点（这里可以理解为，拼接反转的链表段 和 反转的链表段之后的链表段），最后再将preReverse节点的next指针指向endReverse节点（这里可以理解为，拼接反转的链表段之前的链表端 和 反转的链表段）。

注意：由于left可能为1，所以需要考虑preReverse节点为空的情况，此时则不需要拼接反转的链表段之前的链表端 和 反转的链表段。

此过程仅需要一次链表的遍历，所以时间复杂度为O(n)，空间复杂度为O(1)。

3）代码

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode curr = head;
    int start = 1;
    ListNode preReverse = null;
    // 找到要开始反转的链表节点
    while (head.next != null && start++ < left) {
        preReverse = head;
        head = head.next;
    }
    ListNode next = reverseRange(head, right - left);
    // 如果left = 1，则表示从头开始翻转链表；即：preReverse则为null。
    if (preReverse == null) {
        return next;
    }
    // 反转链表段的前一个节点的next引用指向 反转链表段反转后的头结点
    preReverse.next = next;
    return curr;
}

private ListNode reverseRange(ListNode head, int interval) {
    ListNode startReverse = head;
    ListNode next = null;
    ListNode prev = null;
    for (int reversedCount = 0; reversedCount <= interval; reversedCount++) {
        next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    //  开始反转的节点(即链表反转后的尾节点) 的 next引用指向 反转后剩余的链表段
    startReverse.next = next;
    return prev;
}

4、LeetCode 25 K个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

1）示例

提示：

• 链表中节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

2）思路

这里我们可以借鉴LeetCode 92 反转链表 II的思路，既然需要按组反转链表，我们可以先找出第一组把它反转、然后拼接上后面未反转的部分；然后从第二次开始 找出一组把它反转，接着拼接上已经反转的部分、这次反转的部分、未反转的部分，直到最后剩余的链表段不够一组时，直接拼接上剩余的链表段。

算法细节：

1. 链表段分为已反转部分 + 将要反转的部分 + 未反转的部分；
2. 首先要找到第一组可以反转的链表段，反转链表后，获取到新链表的head；并记录下这一组反转之后的链表段的结尾节点lastEnd；
3. 当lastEnd的next指针不为空时，即还存在未反转的链表段时，从lastEnd.next节点开始找出一组要反转的链表段，如果找不出一组，则直接返回。
   否者，反转这一组链表段（并将未反转的链表段拼接到 这一组反转后的链表段 之后），然后拼接上之前反转的链表段（即：将上一组反转后的结尾节点lastEnd的next引用 指向 当前组 反转前的结尾节点end（即：反转后的头节点））；其次再将lastEnd赋值为当前组反转后的 结尾节点。重复步骤3。
4. 最后返回新链表的head。

此过程理论上仅需要一次链表的遍历，但是每次找一组链表段时会多遍历链表的一段，所以可以粗略的认为遍历两次链表，然而时间复杂度依旧为O(n)，空间复杂度为O(1)。

3）代码

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode start = head;
    ListNode end = getKGroupEnd(start, k);
    // 第一组没凑齐
    if (end == null) {
        return head;
    }
    // 第一组凑齐了
    head = end;
    reverse(start, end);
    // 记录下来 上一组反转后的 结尾节点
    ListNode lastEnd = start;
    while (lastEnd.next != null) {
        start = lastEnd.next;
        end = getKGroupEnd(start, k);
        // 下一组不够k个节点
        if (end == null) {
            return head;
        }
        reverse(start, end);
        // 上一组反转后的结尾节点leastEnd的next引用 指 当前组 反转前的结尾节点（即：反转后的头节点）
        lastEnd.next = end;
        // 继续下一组
        lastEnd = start;
    }
    return head;
}

/**
 * K个节点一分组，当前组的最后一个节点
 *
 * @param start 当前组的开始节点
 * @param k     一组中节点的个数
 * @return ListNode 返回当前组的最后一个节点
 */
private ListNode getKGroupEnd(ListNode start, int k) {
    while (--k != 0 && start != null) {
        start = start.next;
    }
    return start;
}

/**
 * 反转某个链表段，并将反转后的链表段 和 剩余的链表段 连到一起
 *
 * @param start 开始要反转的节点
 * @param end   要反转的最后一个节点
 */
private void reverse(ListNode start, ListNode end) {
    // 反转链表段的后一个节点
    end = end.next;
    ListNode pre = null;
    ListNode cur = start;
    ListNode next;
    while (cur != end) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    // 链表段反转后的尾节点 指向 反转链表段的后一个节点
    start.next = end;
}

5、总结

链表相关的题目，关键点在于对引用对象的理解、next指针的指向问题，只要理解清引用对象的概念、next指针的变化，链表反转类型的题目都很容易拼出来。