与数学中的开区间、闭区间相同，下边中，对于[a, b)，如果a、b为指针

[a表示a指针的右边（包含a）
b)表示b指针的左边（不包含b）

一、相交链表

160. 相交链表↗

简单

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

图示两个链表在节点 c1 开始相交

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

1.1 暴力

先用最朴素的while循环分别得到链表A、B的长度

然后再用最朴素的while循环|lengthA - lengthB|次，让他们尾部对齐

最后一起向后遍历即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * 160. 相交链表（暴力）
     *
     * @param headA 	头节点A
     * @param headB		头节点B
     * @return 			相交节点
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        int lengthA = 0, lengthB = 0;
        // 得到链表A、B的长度
        while (a != null) {
            lengthA++;
            a = a.next;
        }
        while (b != null) {
            lengthB++;
            b = b.next;
        }

        ListNode ln1, ln2;
        // 保证ln1的长度小于等于ln2
        if (lengthA < lengthB) {
            ln1 = headA;
            ln2 = headB;
        } else {
            ln1 = headB;
            ln2 = headA;
            int temp = lengthA;
            lengthA = lengthB;
            lengthB = temp;
        }

        // 逐差，让两个链表尾对齐
        while (lengthB > lengthA) {
            ln2 = ln2.next;
            lengthB--;
        }

        while (ln1 != null && ln2 != null) {
            if (ln1 == ln2) return ln1;
            ln1 = ln1.next;
            ln2 = ln2.next;
        }
        return null;
    }
}

时间复杂度 O(m + n) + O(|m - n|) + O(min(m, n)) = O(m + n)

执行用时1ms，击败97.46%，复杂度O(m + n)

消耗内存52.11MB，击败7.02%，复杂度O(1)

1.2 哈气

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * 160. 相交链表（哈希）
     *
     * @param headA 	头节点A
     * @param headB		头节点B
     * @return 			相交节点
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}

执行用时11ms，击败5.92%，复杂度O(m + n)

消耗内存51.47MB，击败56.15%，复杂度O(m)

1.3 双指针

指针a先遍历A链表后遍历B链表，总路程m + n

指针b先遍历B链表后遍历A链表，总路程n + m

这样两个指针会在同一时间走过相同长度的路径，如果有交点就会在交点相遇

6cfcc00a-23da-432c-8cc0-5c9af838aa8f

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * 160. 相交链表（双指针）
     *
     * @param headA 	头节点A
     * @param headB		头节点B
     * @return 			相交节点
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
    }
}

执行用时1ms，击败97.46%，复杂度O(m + n)

消耗内存51.96MB，击败22.00%，复杂度O(1)

二、反转链表

206. 反转链表↗

简单

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

2.1 迭代

用两个指针：curr指向当前节点，prev指向前一个节点

循环过程中，用一个指针next记录curr后一个节点的地址

反转curr和prev的指向顺序，然后将这俩个指针往右推移一个节点

class Solution {
    /**
     * 206. 反转链表（迭代）
     *
     * @param head 	头节点
     * @return 		反转后的头节点
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

2.2 递归

class Solution {
    /**
     * 206. 反转链表（递归）
     *
     * @param head 	头节点
     * @return 		反转后的头节点
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode next = reverseList(head.next);
        
        head.next.next = head;	// A->B->C，改成A->B->A
        head.next = null;		// (A->)B->A，括号内的A->B指向断掉
        
        return next;
    }
}

三、环形链表

141. 环形链表↗

简单

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

3.1 快慢指针

快慢指针：定义一个fast指针和slow指针，其中fast和slow指针存在特定的位移差
速度：例如fast每次移动 2 个节点，slow每次移动 1 个节点
时间：例如fast先走 2 个节点后，slow再开始走

用快慢指针的速度差来进行逐差，当发生追及相遇时，说明链表有环

public class Solution {
    /**
     * 141. 环形链表（快慢指针）
     *
     * @param head 	头节点
     * @return 		是否有环
     */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }
}

四、回文链表

234. 回文链表↗

简单

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

4.1 翻转一半

先用快慢指针方式找到链表中点，翻转右半部分的链表

然后从头节点和中点同时遍历，比较每个节点的值是否相同即可

class Solution {
    /**
     * 234. 回文链表（快慢指针+翻转链表）
     *
     * @param head 	头节点
     * @return 		是否为回文链表
     */
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode r = reverseList(slow);
        ListNode l = head;
        while (r != null && r.val == l.val) {
            r = r.next;
            l = l.next;
        }
        return r == null;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

执行用时4ms，击败87.57%，复杂度O(N)

消耗内存92.54MB，击败62.83%，复杂度O(1)

五、环形链表 II

142. 环形链表 II↗

中等

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

5.1 哈气

不断把当前节点加入Set<ListNode> set中，如果出现重复节点，那么一定是头节点

public class Solution {
    /**
     * 142. 环形链表 II（哈希）
     *
     * @param head 	头节点
     * @return 		环的起始节点
     */
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) return head;
            set.add(head);
            head = head.next;
        }
        return null;
    }
}

执行用时5ms，击败15.95%，复杂度O(N)

消耗内存45.86MB，击败51.25%，复杂度O(N)

5.2 快慢指针

本题利用的是速度差，fast指针走过的路程是slow的两倍，即：fast多走的路程 = slow走过的路程

设头节点到入环节点的长度为a，环长为c，fast走过的路程s_f，slow走过的路程s_s

∵s_f - s_s = kc，k∈N^*\\ s_f = 2s_s\\ ∴ s_s = kc，k∈N^*\\ 慢指针已经在环中走过了(kc-a)\%c的路程\\也就是说再走a步就能使得(kc-a+a)整除c，即到达入环口\\ 而a的定义是头节点到入环节点的长度\\所以只需要同时移动头节点和慢指针直到他们相遇，就是入环口

图解环形链表

public class Solution {
    /**
     * 142. 环形链表 II（快慢指针）
     *
     * @param head 	头节点
     * @return 		环的起始节点
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        if (fast == null || fast.next == null) return null;
        
        while (head != slow) {
            slow = slow.next;
            head = head.next;
        }
        return slow;
    }
}

执行用时0ms，击败100.00%，复杂度O(N)

消耗内存45.75MB，击败74.72%，复杂度O(1)

六、合并两个有序链表

21. 合并两个有序链表↗

简单

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

6.1 迭代（list2插入list1）

用一个虚拟头节点dummy记录头节点的地址，将list2的值按顺序插入list1中

cur指针左边保护了已经合并完的节点，自己及右边是待合并的节点

设链表1的当前节点p1，链表2当前节点p2

如果当前p2.val <= p1.val，由于两条链表已经有序，直接将list2当前节点插入到list1中是一定有序的
- 先记录p2下一个节点的地址
- cur的下一个节点指向p2
- p2指回原list1的节点p1
- 将cur和p2向右推动一个节点
如果p2.val > p1.val，说明目前不需要插入，直接将cur沿着list1向右推动一个节点即可

class Solution {
    /**
     * 21. 合并两个有序链表（迭代，将list2插入list1）
     *
     * @param list1 	头节点1
     * @param list2 	头节点2
     * @return 			合并后的链表头节点
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        dummy.next = list1;

        ListNode cur = dummy;
        ListNode p1 = list1, p2 = list2;

        while (p1 != null && p2 != null) {
            if (p2.val <= p1.val) {
                ListNode nextP2 = p2.next;
                cur.next = p2;
                p2.next = p1;

                cur = p2;
                p2 = nextP2;
            } else {
                cur = p1;
                p1 = p1.next;
            }
        }
        if (p2 != null) cur.next = p2;

        return dummy.next;
    }
}

6.2 迭代（两个一起插）

6.1 的思路还可以优化一下，cur的作用保持不变

cur指针左边保护了已经合并完的节点，自己及右边是待合并的节点

如果当前list2.val <= list1.val，则将list2的节点插入到cur.next，向右推动list2一个节点
否则将list1的节点插入到cur.next，向右推动list1一个节点

class Solution {
    /**
     * 21. 合并两个有序链表（迭代）
     *
     * @param list1 	头节点1
     * @param list2 	头节点2
     * @return 			合并后的链表头节点
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        
        while (list1 != null && list2 != null) {
            if (list2.val <= list1.val) {
                cur.next = list2;
                list2 = list2.next;
            } else {
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        
        cur.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}

6.3 递归

如果当前list2.val <= list1.val，则将list2的节点插入到cur.next，向右推动list2一个节点
否则将list1的节点插入到cur.next，向右推动list1一个节点

上边 6.2 的cur可以用递归的方式实现

class Solution {
    /**
     * 21. 合并两个有序链表（递归）
     *
     * @param list1 	头节点1
     * @param list2 	头节点2
     * @return 			合并后的链表头节点
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

七、两数相加

2. 两数相加↗

中等

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

7.1 原地修改

本题本质上是数学中的列竖式相加，不过是反过来的

输入：l1 = [9,9,9,9,9], l2 = [9,9]输出：[8,9,0,0,0,1]

805905bc-d92c-4051-bd90-a8bfbd0ce51e

那我们只需要用最朴素的while循环找到更长的那条链表，令他为l1，放在竖式的最上方

另一条短的链表l2放在下方，就可以从右往左开始相加，并用一个lead变量记录进位

如果l1已经走到了末尾，即l1 = null，此时是没法再直接新增一个节点的
所以我们需要一个prev指针，来指向最后一次操作的数字，以处理最后的溢出进位（即100098的1）

class Solution {
    /**
     * 2. 两数相加（暴力）
     *
     * @param l1 	头节点1
     * @param l2 	头节点2
     * @return 		相加后的链表头节点
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode list1 = l1, list2 = l2;
        while (list1 != null && list2 != null) {
            list1 = list1.next;
            list2 = list2.next;
        }
        if (list1 == null) return helper(l2, l1);
        else return helper(l1, l2);
    }

    // addTwoNumbers 中已经保证了 l1.length >= l2.length
    public ListNode helper(ListNode l1, ListNode l2) {
        int lead = 0;	// 进位
        ListNode head1 = l1, prev = l1;

        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + lead;
            l1.val = sum % 10;
            lead = sum / 10;

            // 移动指针
            prev = l1;
            l1 = l1.next;
            l2 = l2.next;
        }

        // 处理剩下的位数
        while (l1 != null) {
            int sum = l1.val + lead;
            l1.val = sum % 10;
            lead = sum / 10;
            prev = l1;
            l1 = l1.next;
        }

        if (lead == 1) prev.next = new ListNode(1);	// 溢出补1

        return head1;
    }
}

执行用时1ms，击败100.00%，复杂度O(max(m, n))

消耗内存45.90MB，击败9.19%，复杂度O(1)

7.2 创建新链表

7.1暴力解法遍历了两次链表，能不能只遍历一次链表呢？

由于我们是直接在原链表做修改，只遍历一次链表势必会导致复杂的讨论

所以我们可以定义一个新的链表用来存储加法的结果，这样子可以避免长短的讨论

class Solution {
    /**
     * 2. 两数相加（创建新链表）
     *
     * @param l1 	头节点1
     * @param l2 	头节点2
     * @return 		相加后的链表头节点
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        int lead = 0;

        while (l1 != null || l2 != null || lead != 0) {
            int num1 = (l1 != null) ? l1.val : 0;
            int num2 = (l2 != null) ? l2.val : 0;
            int sum = num1 + num2 + lead;

            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            lead = sum / 10;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

执行用时1ms，击败100.00%，复杂度O(max(m, n))

消耗内存45.58MB，击败77.78%，复杂度O(1)

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

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

中等

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

8.1 暴力

暴力思路不难想，先用最朴素的while循环求出链表长度，然后再倒推n个，就知道下次遍历的时候要删掉谁了，下边直接贴出官方题解

class Solution {
    /**
     * 19. 删除链表的倒数第 N 个结点（暴力）
     *
     * @param head 	头节点
     * @param n 	倒数要删除的节点次序
     * @return 		删除该节点后的链表头节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

8.2 快慢指针

本题利用的是时间差，先让快指针走n步，随后启动慢指针，则他们刚好差n个，当快指针走到头，慢指针恰好指向倒数第n个

class Solution {
    /**
     * 19. 删除链表的倒数第 N 个结点（快慢指针）
     *
     * @param head 	头节点
     * @param n 	倒数要删除的节点次序
     * @return 		删除该节点后的链表头节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        
        ListNode fast = head;
        ListNode slow = dummy;
        
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        
        // 延时启动
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 删除节点
        slow.next = slow.next.next;
        return dummy.next;
    }
}

九、两两交换链表中的节点

24. 两两交换链表中的节点↗

中等

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

9.1 暴力

用四个指针指向操作区域，不断交换中间两个指针指向的节点，然后集体向右移动三个节点即可

prot指针，左边保护已经交换完的链表，此处为prot]
prev指针，指向交换前的奇数节点
curr指针，指向交换前的偶数节点
next指针，指向两个交换节点的下一个节点

38e17fc3-f47f-4c8b-ace2-ab309cc3e024

class Solution {
    /**
     * 24. 两两交换链表中的节点（暴力）
     *
     * @param head 	头节点
     * @return 		交换节点后的链表
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prot = dummy, prev = prot.next, curr = prev.next, next = curr.next;
        
        while (next != null && next.next != null) {
            prev.next = next;
            curr.next = prev;
            prot.next = curr;
            
            prot = prev;
            prev = next;
            curr = next.next;
            next = next.next.next;
        }
		// 不管总节点个数是奇数还是偶数，最后一次交换都由于 next == null || next.next == null 没有完成
        prev.next = next;
        curr.next = prev;
        prot.next = curr;
        return dummy.next;
    }
}

9.2 暴力的小优化

注意到curr指针和next指针可以在每次循环交换操作前，由prev.next和prev.next.next得到

可以将curr指针和next指针定义为循环内部的变量，这样子就少写了最后一次循环外的交换操作的代码

class Solution {
    /**
     * 24. 两两交换链表中的节点（迭代）
     *
     * @param head 	头节点
     * @return 		交换节点后的链表
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prot = dummy, prev = prot.next;
        
        while (prev != null && prev.next != null) {
            ListNode curr = prev.next, next = curr.next;
            prev.next = next;
            curr.next = prev;
            prot.next = curr;
            
            prot = prev;
            prev = next;
        }

        return dummy.next;
    }
}

十、K 个一组翻转链表

25. K 个一组翻转链表↗

困难

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

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

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

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

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

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

10.1 迭代

用一个计数器count记录已经遍历过的节点数，当达到k时，清空计数器，并对这些节点调用reverseList进行局部翻转

用prot]保护左边已经处理完的链表，[start, end)表示要翻转的区间

以k = 2时为例，节点1、2仅仅翻转后，指针的指向如下图所示

则指针的重新连接顺序应该是：

prot.next = head
start.next = end

然后将prot]向右推动到节点1的位置

3fe59847-e567-4945-bbaa-719a30b6c872

class Solution {
    /**
     * 25. K 个一组翻转链表（迭代）
     *
     * @param head 	头节点
     * @return 		交换节点后的链表
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prot = dummy;
        int count = 0;

        while (head != null) {
            count++;
            if (count == k) {
                ListNode start = prot.next;
                ListNode end = head.next;     // 翻转[start, end)内的节点
                
                // 链表重新连接
                prot.next = reverseList(start, end);
                start.next = end;
                
                // 移动指针
                head = start;
                prot = start;
                
                count = 0;
            }
            
            head = head.next;
        }
        return dummy.next;
    }

    private ListNode reverseList(ListNode start, ListNode end) {
        ListNode prev = end;
        while (start != end) {
            ListNode next = start.next;
            start.next = prev;
            prev = start;
            start = next;
        }
        return prev;
    }
}

十一、随机链表的复制

138. 随机链表的复制↗

中等

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝↗。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random 为 null 或指向链表中的节点。

11.1 哈气

创建一个Map<旧Node，新Node>的哈希表，映射旧节点和拷贝后的新节点

先遍历一遍链表，将所有节点存入Map

再遍历一遍链表，将节点串联起来

class Solution {
    /**
     * 138. 随机链表的复制（哈气）
     *
     * @param head 	头节点
     * @return 		深拷贝后的头节点
     */
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();

        for (Node h = head; h != null; h = h.next) map.put(h, new Node(h.val));

        for (Node h = head; h != null; h = h.next) {
            Node node = map.get(h);
            node.next = map.get(h.next);
            node.random = map.get(h.random);
        }

        return map.get(head);
    }
}

11.2 不用哈希表

步骤1：在原链表每个节点后面插入新节点

原链表: A → B → C
变为:   A → A' → B → B' → C → C'

步骤2：赋值random

对于每个A节点

A'.random = A.random == null ? null : A.random.next

步骤3：断链，拆成新旧两个链表

class Solution {
    public Node copyRandomList(Node head) {
        // 交替插入节点
        for (Node h = head; h != null; h = h.next.next) 
            h.next = new Node(h.val, h.next);
        
        // 处理随机指针
        for (Node h = head; h != null; h = h.next.next) 
            if (h.random != null)  h.next.random = h.random.next;

        // 分离链表
        Node dummy = new Node(0);
        Node cur = dummy;
        for (Node h = head; h != null; h = h.next, cur = cur.next) {
            Node n = h.next; // 深拷贝后的新节点
            cur.next = n;
            h.next = n.next; // 恢复原节点的 next
        }

        return dummy.next;
    }
}

十二、排序链表

148. 排序链表↗

中等

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

12.1 归并排序

用快慢指针找到链表中点，断开链表，排序一半的链表，然后两两合并有序链表

class Solution {
    /**
     * 148. 排序链表（递归）
     *
     * @param head 	头节点
     * @return 		排序后的链表头节点
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        // 快慢指针找中点，断开成两段
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;

        // 分治排序左右两链表
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // 合并
        return mergeTwoLists(left, right);
    }

    /**
     * 21. 合并两个有序链表（递归）
     *
     * @param list1 	头节点1
     * @param list2 	头节点2
     * @return 			合并后的链表头节点
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

执行用时23ms，击败8.12%，复杂度O(N log N)

消耗内存63.65MB，击败5.03%，复杂度O(log N)

十三、合并 K 个升序链表

23. 合并 K 个升序链表↗

困难

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

13.1 暴力两两合并

将lists[0]和lists[1]合并后放回lists[1]

将lists[1]和lists[2]合并后放回lists[2]

…

class Solution {
    /**
     * 23. 合并 K 个升序链表（暴力）
     *
     * @param lists 	待合并的链表
     * @return 			合并后的链表头节点
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        for (int i = 1; i < lists.length; i++) {
            lists[i] = mergeTwoLists(lists[i - 1], lists[i]);
        }
        return lists[lists.length - 1];
    }

    /**
     * 21. 合并两个有序链表（递归）
     *
     * @param list1 	头节点1
     * @param list2 	头节点2
     * @return 			合并后的链表头节点
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

有 k 个链表
每个链表平均长度为 n
总节点数 N = k × n

执行用时314ms，击败5.03%，复杂度O(kN)

消耗内存45.98MB，击败73.19%，复杂度O(N)

13.2 暴力优化

13.1 中每个链表都被访问了多次，复杂度来到

class Solution {
    /**
     * 23. 合并 K 个升序链表（迭代）
     *
     * @param lists 	待合并的链表
     * @return 			合并后的链表头节点
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int length = lists.length, mid = lists.length / 2;   
        while (length > 1) {
            mid = (length + 1) / 2;
            for (int i = 0; i < length / 2; i++) {
                lists[i] = mergeTwoLists(lists[i], lists[length - i - 1]);
            }
            length = mid;
        }
        return lists[0];
    }

    /**
     * 21. 合并两个有序链表（递归）
     *
     * @param list1 	头节点1
     * @param list2 	头节点2
     * @return 			合并后的链表头节点
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

执行用时3ms，击败64.48%，复杂度O(N log k)

消耗内存45.97MB，击败73.94%，复杂度O(N)

十四、LRU 缓存

146. LRU 缓存↗

中等

请你设计并实现一个满足 LRU (最近最少使用) 缓存↗ 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多调用 2 * 10^5 次 get 和 put

14.1 双向链表

class LRUCache {
    private class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) {
            this.key = k;
            this.value = v;
        }
    }

    private int capacity;
    private Node dummy;
    private Map<Integer, Node> map;

    
    /**
     * 146. LRU 缓存（双向链表）
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.dummy = new Node(0, 0);
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        removeNode(node);
        insertHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            removeNode(node);
            insertHead(node);
        } else {
            node = new Node(key, value);
            insertHead(node);
            map.put(key, node);
        }

        if (map.size() > capacity) {
            Node tail = dummy.prev;
            removeNode(tail);
            map.remove(tail.key);
        }
    }

    // 把 node 从链表中移除
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 把 node 插到链表头部（dummy之后）
    private void insertHead(Node node) {
        node.next = dummy.next;
        node.prev = dummy;
        dummy.next.prev = node;
        dummy.next = node;
    }
}

Thanks for reading!

力扣hot100-《链表》章节题解

周五 2月 06 2026 链表

8844 字 · 53 分钟

algorithm leetcode hot100 linked list

Yiiyye's Blog

欲买桂花同载酒，终不似，少年游！

力扣hot100-《链表》章节题解

一、相交链表

1.1 暴力

1.2 哈气

1.3 双指针

二、反转链表

2.1 迭代

2.2 递归

三、环形链表

3.1 快慢指针

四、回文链表

4.1 翻转一半

五、环形链表 II

5.1 哈气

5.2 快慢指针

六、合并两个有序链表

6.1 迭代（list2插入list1）

6.2 迭代（两个一起插）

6.3 递归

七、两数相加

7.1 原地修改

7.2 创建新链表

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

8.1 暴力

8.2 快慢指针

九、两两交换链表中的节点

9.1 暴力

9.2 暴力的小优化

十、K 个一组翻转链表

10.1 迭代

十一、随机链表的复制

11.1 哈气

11.2 不用哈希表

十二、排序链表

12.1 归并排序

十三、合并 K 个升序链表

13.1 暴力两两合并

13.2 暴力优化

十四、LRU 缓存

14.1 双向链表

力扣hot100-《链表》章节题解