跳到主要内容

链表

链表是一种通过指针串联节点的线性数据结构。与数组不同，链表的节点在内存中不必连续存储，这使得它在插入和删除操作上具有天然优势，但也失去了随机访问的能力。

理解链表的本质​

为什么需要链表？​

数组虽然支持 O(1)O(1) 随机访问，但有两个致命弱点：

  1. 大小固定，无法动态扩展
  2. 插入删除需要 O(n)O(n) 移动元素

链表正是为了解决这些问题而生。它通过指针将分散的节点连接起来，可以在 O(1)O(1) 时间内插入或删除节点（前提是已知位置）。

链表的代价​

天下没有免费的午餐。链表的灵活性带来了代价：

  • 失去随机访问：无法通过下标直接访问，必须从头遍历
  • 额外空间：每个节点需要存储指针
  • 缓存不友好：节点分散在内存各处，不利于 CPU 缓存

适用场景​

场景推荐使用
频繁在头部插入删除链表
需要随机访问数组
数据大小未知链表
内存受限需要紧凑存储数组
实现哈希表的拉链法链表

链表的实现​

单链表​

单链表的每个节点包含数据和指向下一个节点的指针。

public class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) { this.val = val; }
}

public class SinglyLinkedList {
    private ListNode head;
    private int size;
    
    // 在头部插入 - O(1)
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 在尾部插入 - O(n)
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    // 在指定位置插入 - O(n)
    public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            addFirst(val);
            return;
        }
        
        // 找到前驱节点
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }
    
    // 删除头部 - O(1)
    public int removeFirst() {
        if (head == null) {
            throw new IllegalStateException("List is empty");
        }
        int val = head.val;
        head = head.next;
        size--;
        return val;
    }
    
    // 删除指定位置 - O(n)
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            return removeFirst();
        }
        
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        
        int val = prev.next.val;
        prev.next = prev.next.next;
        size--;
        return val;
    }
    
    // 查找 - O(n)
    public int indexOf(int val) {
        ListNode current = head;
        int index = 0;
        while (current != null) {
            if (current.val == val) return index;
            current = current.next;
            index++;
        }
        return -1;
    }
}

双链表​

双链表的每个节点有前驱和后继两个指针，可以双向遍历。

public class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
    
    DoublyListNode(int val) { this.val = val; }
}

public class DoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode tail;
    private int size;
    
    // 在头部插入 - O(1)
    public void addFirst(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }
    
    // 在尾部插入 - O(1)
    public void addLast(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (tail == null) {
            head = tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // 删除头部 - O(1)
    public int removeFirst() {
        if (head == null) {
            throw new IllegalStateException("List is empty");
        }
        int val = head.val;
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        size--;
        return val;
    }
    
    // 删除尾部 - O(1)
    public int removeLast() {
        if (tail == null) {
            throw new IllegalStateException("List is empty");
        }
        int val = tail.val;
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        size--;
        return val;
    }
}

双链表 vs 单链表：

特性单链表双链表
头部操作O(1)O(1)
尾部操作O(n)O(1)
空间开销每节点 1 个指针每节点 2 个指针
反向遍历不支持支持

Java 的 LinkedList 就是双链表的实现。

核心技巧​

虚拟头节点（Dummy Node）​

链表操作中，头节点是最麻烦的：它没有前驱节点，需要特殊处理。虚拟头节点（哨兵节点）可以统一所有操作。

不使用虚拟头节点：

public ListNode deleteNode(ListNode head, int val) {
    // 特殊处理：删除的是头节点
    if (head.val == val) {
        return head.next;
    }
    
    ListNode prev = head;
    while (prev.next != null) {
        if (prev.next.val == val) {
            prev.next = prev.next.next;
            break;
        }
        prev = prev.next;
    }
    return head;
}

使用虚拟头节点：

public ListNode deleteNode(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode prev = dummy;
    while (prev.next != null) {
        if (prev.next.val == val) {
            prev.next = prev.next.next;
            break;
        }
        prev = prev.next;
    }
    return dummy.next;
}

虚拟头节点让所有节点的操作都变成"对 prev.next 操作"，代码更简洁，也更不容易出错。

快慢指针​

快慢指针是处理链表问题的神器。两个指针以不同速度前进，可以解决很多看似需要多次遍历的问题。

核心思想：快指针先走，慢指针后走，利用两者之间的距离关系。

找链表中点​

public ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;           // 慢指针走一步
        fast = fast.next.next;      // 快指针走两步
    }
    
    return slow;  // 当快指针到末尾时，慢指针在中点
}

为什么这样能找到中点？

想象两个人在跑道上跑步，甲的速度是乙的两倍。当甲跑完全程时，乙刚好跑了一半。

删除倒数第 N 个节点​

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy, slow = dummy;
    
    // 快指针先走 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // 快慢指针同时前进
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 此时 slow 指向倒数第 n+1 个节点
    slow.next = slow.next.next;
    
    return dummy.next;
}

关键点：快指针先走 n+1 步（不是 n 步），这样当快指针到达 null 时，慢指针正好在倒数第 n+1 个位置，即待删除节点的前驱。

检测环形链表​

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;
    
    ListNode slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) return true;  // 相遇说明有环
    }
    
    return false;
}

为什么快慢指针一定会相遇？

把链表想象成一个环形跑道。快指针每次比慢指针多走一步，相当于快指针在"追赶"慢指针。每一步，两者之间的距离减少 1，最终一定会追上。

找到环的入口：

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    // 第一步：判断是否有环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    
    if (fast == null || fast.next == null) return null;  // 无环
    
    // 第二步：找到入口
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

原理解释：

设环外部分长度为 aa，相遇点到环入口的距离为 bb，环长为 cc。

  • 慢指针走了 a+ba + b 步
  • 快指针走了 a+b+nca + b + nc 步（nn 是快指针多绕的圈数）
  • 快指针步数是慢指针的两倍：2(a+b)=a+b+nc2(a + b) = a + b + nc
  • 得到：a=nc−b=(n−1)c+(c−b)a = nc - b = (n-1)c + (c-b)

这意味着从相遇点和从头节点同时出发，走 aa 步后会相遇在环入口。

链表反转​

反转链表是最基础也最重要的链表操作。

迭代法​

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode next = curr.next;  // 保存下一个节点
        curr.next = prev;           // 反转指针
        prev = curr;                // 前移 prev
        curr = next;                // 前移 curr
    }
    
    return prev;
}

递归法​

public ListNode reverseListRecursive(ListNode head) {
    // 基准情况：空链表或只有一个节点
    if (head == null || head.next == null) {
        return head;
    }
    
    // 递归反转剩余部分
    ListNode newHead = reverseListRecursive(head.next);
    
    // 将当前节点接到反转后的链表末尾
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

区间反转（反转 [left, right] 区间）​

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    // 找到反转区间的前一个节点
    ListNode prev = dummy;
    for (int i = 0; i < left - 1; i++) {
        prev = prev.next;
    }
    
    // 反转区间内的节点
    ListNode curr = prev.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    
    return dummy.next;
}

技巧：这段代码使用了"头插法"，每次将下一个节点插到反转区间的头部，而不是交换节点值。

K 个一组反转​

public ListNode reverseKGroup(ListNode head, int k) {
    // 检查剩余节点是否够 k 个
    ListNode curr = head;
    int count = 0;
    while (curr != null && count < k) {
        curr = curr.next;
        count++;
    }
    
    if (count < k) return head;  // 不够 k 个，不反转
    
    // 反转前 k 个节点
    ListNode prev = null;
    curr = head;
    for (int i = 0; i < k; i++) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    // head 现在是反转后的尾节点，递归处理剩余部分
    head.next = reverseKGroup(curr, k);
    
    return prev;  // prev 是反转后的头节点
}

经典问题详解​

合并两个有序链表​

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    // 接上剩余部分
    curr.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

关键点：使用虚拟头节点避免处理头节点的特殊情况。

相交链表​

找到两个链表的交点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    
    ListNode a = headA, b = headB;
    
    // 指针走完自己的链表后，走向另一个链表
    // 如果有交点，两个指针会在交点相遇
    // 如果没有交点，两个指针会同时为 null
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    
    return a;
}

原理：

设链表 A 独有部分长度为 aa，链表 B 独有部分长度为 bb，公共部分长度为 cc。

  • 指针 A 走了 a+c+ba + c + b 步
  • 指针 B 走了 b+c+ab + c + a 步
  • 两者走的步数相同，所以会在交点相遇

回文链表​

判断链表是否是回文。

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    
    // 找中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 反转后半部分
    ListNode secondHalf = reverseList(slow.next);
    
    // 比较前后两半
    ListNode p1 = head, p2 = secondHalf;
    while (p2 != null) {
        if (p1.val != p2.val) return false;
        p1 = p1.next;
        p2 = p2.next;
    }
    
    return true;
}

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

注意：这里找中点时使用 fast.next != null && fast.next.next != null，这样当链表长度为偶数时，slow 停在左半部分的最后一个节点，便于处理。

排序链表​

对链表进行 O(nlog⁡n)O(n \log n) 排序。

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);
}

这里使用了归并排序，因为链表归并不需要额外空间。

常见错误​

空指针异常​

// 错误：没有检查 head 是否为空
while (head.next != null) { ... }

// 正确
while (head != null && head.next != null) { ... }

链表断裂​

// 错误：先断开链表，丢失后续节点
curr.next = prev;
ListNode next = curr.next;  // 此时 curr.next 已经是 prev 了！

// 正确：先保存再断开
ListNode next = curr.next;
curr.next = prev;

忘记返回值​

// 错误：递归时忘记处理返回值
reverseListRecursive(head.next);

// 正确
ListNode newHead = reverseListRecursive(head.next);

小结​

链表操作的核心在于指针的正确维护。掌握以下几点：

  1. 虚拟头节点：统一处理，避免特殊情况
  2. 快慢指针：一次遍历解决需要多次遍历的问题
  3. 画图思考：链表问题一定要画图，理清指针变化
  4. 先保存再修改：避免链表断裂

链表题目虽然不涉及复杂算法，但对指针操作要求很高。多练习、多画图是掌握链表的关键。

练习​

基础：

  1. LeetCode 206：反转链表
  2. LeetCode 21：合并两个有序链表
  3. LeetCode 141：环形链表
  4. LeetCode 83：删除排序链表中的重复元素

进阶： 5. LeetCode 19：删除链表的倒数第 N 个节点 6. LeetCode 876：链表的中间结点 7. LeetCode 160：相交链表 8. LeetCode 234：回文链表 9. LeetCode 142：环形链表 II 10. LeetCode 148：排序链表

挑战： 11. LeetCode 25：K 个一组翻转链表 12. LeetCode 23：合并 K 个升序链表 13. LeetCode 143：重排链表