• 基础知识：链表如何实现，如何遍历链表。链表可以保证头部尾部插入删除操作都是O（1），查找任意元素位置O（N）
• 基础题目：

Leetcode 206. Reverse Linked List

Leetcode 876. Middle of the Linked List

注意：快慢指针和链表反转几乎是所有链表类问题的基础，尤其是反转链表，代码很短，建议直接背熟。

• 进阶题目:

Leetcode 160. Intersection of Two Linked Lists

Leetcode 141. Linked List Cycle (Linked List Cycle II)

Leetcode 92. Reverse Linked List II

Leetcode 328. Odd Even Linked List

Leetcode 206. Reverse Linked List

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->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;
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是链表的长度。

空间复杂度：$O(1)O(1)$。只需要常数的空间存放若干变量。

Leetcode 876. Middle of the Linked List

题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5]。) 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

解法

使用快慢指针，快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针就指向了中间结点。

代码

class Solution {
    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;
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是链表的长度。快指针需要遍历链表一次，所以时间复杂度为 $O(n)O(n)$。

空间复杂度：$O(1)O(1)$，只需要常数级别的空间存储快慢指针。

Leetcode 160. Intersection of Two Linked Lists

题目描述

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

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

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,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
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

提示：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解法

本题的解法是使用双指针法。我们分别用指针 $p_{1}p\_1$ 和 $p_{2}p\_2$ 遍历链表 $AA$ 和 $BB$，当指针到达链表的末尾时，将其指向另一个链表的头部，直到两个指针相遇。如果两个链表相交，那么两个指针相遇的节点就是相交节点，否则两个指针都会指向 $nullnull$。

为了保证时间复杂度为 $O(n)O(n)$，我们需要先遍历两个链表，计算出它们的长度差 $lenlen$，然后让指针 $p_{1}p\_1$ 先走 $lenlen$ 步。然后 $p_{1}p\_1$ 和 $p_{2}p\_2$ 同时向前移动，直到相遇。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            p1 = (p1 != null) ? p1.next : headB;
            p2 = (p2 != null) ? p2.next : headA;
        }
        return p1;
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是两个链表的长度之和。指针 $p_{1}p\_1$ 最多走 $nn$ 步，指针 $p_{2}p\_2$ 最多走 $nn$ 步。因此，总时间复杂度为 $O(n)O(n)$。

空间复杂度：$O(1)O(1)$。我们只需要两个指针即可。

Leetcode 141. Linked List Cycle (Linked List Cycle II)

题目描述

给定一个链表，判断链表中是否有环。

如果链表中存在环，则返回 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 或者链表中的一个 有效索引 。

解法

本题解法是使用快慢指针，快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，那么快指针一定会追上慢指针，此时返回 true。如果链表中不存在环，那么快指针一定会到达链表的末尾，此时返回 false。

代码

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是链表中的节点数。最坏情况下，快指针需要走完整个链表，因此时间复杂度是 $O(n)O(n)$。

空间复杂度：$O(1)O(1)$，只需要常数的额外空间。

Leetcode 92. Reverse Linked List II

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

解法

首先，我们需要找到需要反转的区间，然后对该区间进行反转。具体来说，我们定义指针 pre 指向第 m-1 个节点，指针 cur 指向第 m 个节点，然后通过迭代，将第 m+1 到第 n 个节点依次插入到第 m 个节点之前，完成区间反转。

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        for (int i = m; i < n; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是链表的长度。我们对链表进行了一次遍历。

空间复杂度：$O(1)O(1)$。我们只需要常数空间存储若干变量。

Leetcode 328. Odd Even Linked List

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里我们讨论的是节点编号的奇偶性，而不是节点的值的奇偶性。

你应该尽量保持奇数节点和偶数节点的相对顺序。

示例 1:

输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

解法

本题的解法是将所有奇数节点和偶数节点分别放到两个链表中，最后将偶数链表接在奇数链表的后面即可。

具体步骤如下：

1. 如果链表为空，直接返回。
2. 初始化奇数链表和偶数链表的头结点 odd 和 even。
3. 遍历链表，将奇数节点连接到奇数链表的后面，偶数节点连接到偶数链表的后面。
4. 将偶数链表接在奇数链表的后面。
5. 将偶数链表的尾节点指向 null，防止出现环。

代码

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        if (even != null) {
            even.next = null;
        }
        return head;
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是链表的长度。需要遍历整个链表。

空间复杂度：$O(1)O(1)$，只需要维护常量级的额外空间。