单链表的六大解题套路

合并两个有序链表


x
// 递归：明确 「当前节点」「该做什么」「什么时候做」「注意返回值」
//  - 当前节点：两个链表的头节点
//  - 该做什么：选择值小的节点，递归下一个节点
//  - 什么时候做：先序 || 后序 都 🉑️
//  - 返回值：子问题的头节点，接在一起即可 「当前节点.next = 子问题返回值」
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    // 处理当前节点
    // 如果两个节点都为 null，说明已经遍历完了两个两边，返回 null
    if (list1 == null && list2 == null) return null;
    // 如果 list1 为 null，说明 list2 没有处理完，直接返回 list2
    if (list1 == null) return list2;
    // 如果 list2 为 null，说明 list1 没有处理完，直接返回 list1
    if (list2 == null) return list1;
    
    // 两个 list 都不为空，选择值小的，递归下一个节点
    if (list1.val < list2.val) {
        // 当前节点.next = 子问题返回值
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

// 非递归
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 虚拟一个假头节点，方便后续处理
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;

    ListNode p1 = list1; // list1 的指针节点
    ListNode p2 = list2; // list2 的指针节点

    // 当 p1 和 p2 均非空时
    while (p1 != null && p2 != null) {
        if (p1.val <= p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = head.next;
    }
    // 当 p1 或 p2 为空时
    p.next = p1 == null ? p2 : p1;

    return dummy.next;
}

合并 K 个升序链表

题目详情可见合并K个升序链表

利用 优先队列 来处理，即 最小堆
每次选择堆顶元素（最小值），并加入「堆顶元素.next」
其实与合并两个链表思路一致，只不过合并两个链表是选择两个元素中的最小值，合并K个链表是选择K个元素中的最小值而已


xxxxxxxxxx
// 如果可以不用递归，就不用递归；非递归的耗时更短
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null) return null;
    Queue<ListNode> pq = new PriorityQueue<>((o1, o2) -> (o1.val - o2.val));
    for (ListNode list : lists) {
        if (list != null) pq.offer(list);
    }
    return mergeKListsHelper(pq);
}

private ListNode mergeKListsHelper(Queue<ListNode> pq) {
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        if (node.next != null) pq.offer(node.next);
        p.next = node;
        p = p.next;
    }
    return dummy.next;
}

环形链表

题目详情可见环形链表

采用快慢指针的方法
slow 每次移动一步；fast 每次移动两步
如果存在环，slow 和 fast 必会相遇


xxxxxxxxxx
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    // 此处不需要判断 slow，如果 fast 不为 null，slow 经过的路径肯定不为 null
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

环形链表 II

题目详情可见环形链表 II

和上面题目的区别：需要返回链表开始入环的第一个节点
k = x + y
2k = x + y + z + y
所以有：x = z
相遇后，令其中一个回到起点，然后以相同的速度移动，再次相遇时即是环起点


xxxxxxxxxx
public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        // 核心代码
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

链表的中间结点

题目详情可见链表的中间结点

利用快慢指针，当 fast 到达终点时，slow 刚好到达中点
当节点数量为奇数时，中间节点正好为 1 个
当节点数量为偶数时，中间节点有 2 个，正好返回第 2 个中间节点


xxxxxxxxxx
public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

相交链表

题目详情可见相交链表

思路：当 A 移动完后，接着从 B 开始移动；同理，当 B 移动完后，接着从 A 开始移动
如果有交点，则会在交点处相遇
如果没有交点，则会移动到 null 处停止 (这个处理太妙了)


xxxxxxxxxx
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA;
    ListNode pB = headB;
    while (pA != pB) {
        if (pA == null) pA = headB;
        else pA = pA.next;
        if (pB == null) pB = headA;
        else pB = pB.next;
    }
    return pA;   
}

删除链表的倒数第 N 个结点

题目详情可见删除链表的倒数第N个结点

先行节点：提前移动N步
后行节点：在先行节点移动完N步后再移动
当先行节点到达表尾时，后行节点的位置即为倒数第N个节点


xxxxxxxxxx
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟一个假头节点，方便后续处理 「head = [1], n = 1」
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // prev 为了删除倒数第N个节点
    ListNode prev = dummy;
    ListNode slow = head;
    ListNode fast = head;
    for (int i = 0; i < n; i++) fast = fast.next;

    while (fast != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next;
    }
    prev.next = slow.next;
    return dummy.next;
}

总结

技巧总结
虚拟头节点，方便处理一些特殊 null 指针情况
快、慢指针套路
求中间节点 / 判断环（两倍速度）
倒数第 N 个节点（fast 先移动 N 步）
确定入环节点（先两倍速度，后一倍速度）
合并链表
两个链表合并（依次比较头节点）
K 个链表合并（利用优先队列，快速得到最小值元素）
链表相交
先走完自己的链表，然后转而走对方链表，相等处即为交点