LeetCode热门100

链表模块 — LeetCode 热门 100 题精讲（Java 向）

从反转链表到 LRU 缓存，双指针、递归、虚拟头结点、哈希表辅助 — 十四道链表高频题全攻略

链表问题概述

链表是线性表的一种链式存储结构，其节点在内存中不连续，通过指针链接。链表题的核心是 指针操作，常涉及头结点的处理、边界条件、环检测、合并、反转、复制等。由于链表不能随机访问，很多操作只能顺序遍历，因此时间复杂度的优化往往依赖于双指针、递归或借助额外数据结构（如哈希表）。

LeetCode 热门 100 题中共有 14 道链表题，覆盖了链表操作的几乎所有经典场景。按照技巧分类，可分为以下几组：

  • 反转与变形：206. 反转链表、234. 回文链表、24. 两两交换链表中的节点、25. K 个一组翻转链表
  • 双指针/快慢指针：141. 环形链表、142. 环形链表 II、160. 相交链表、19. 删除链表的倒数第 N 个结点
  • 合并与加法：21. 合并两个有序链表、2. 两数相加、23. 合并 K 个升序链表
  • 复杂链表操作：138. 随机链表的复制、148. 排序链表
  • 设计类：146. LRU 缓存（哈希表 + 双向链表）

下面按组分别展开，先介绍共性思路，再逐题讲解关键代码和注意点。

一、反转与变形

反转链表是基础操作，其他变形（回文、交换、K 组翻转）往往在反转的基础上增加预处理或分段处理。

206. 反转链表

题目：反转一个单链表。

核心思路：迭代法，维护三个指针 prev、curr、next，逐个改变 curr.next 指向 prev，然后前进。

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

复杂度：时间 O(n)，空间 O(1)。

关键点：必须保存 curr.next 否则断链；返回 prev 成为新头。

234. 回文链表

题目：判断链表是否为回文。要求 O(n) 时间 O(1) 空间。

核心思路：

  1. 快慢指针找中点。
  2. 反转后半部分链表。
  3. 比较前半部分和反转后的后半部分。
public boolean isPalindrome(ListNode head) {
    if (head == null) return true;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode second = reverseList(slow.next);
    ListNode p1 = head, p2 = second;
    while (p2 != null) {
        if (p1.val != p2.val) return false;
        p1 = p1.next;
        p2 = p2.next;
    }
    return true;
}

复杂度：时间 O(n)，空间 O(1)。

关键点：快慢指针找中点时，slow 指向前半部分最后一个节点；反转后半部分后比较，无需恢复。

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

题目：给定链表，两两交换相邻节点，不能改值。

核心思路：迭代使用虚拟头结点，三个节点一组操作。

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next;
        ListNode second = first.next;
        first.next = second.next;
        second.next = first;
        prev.next = second;
        prev = first;
    }
    return dummy.next;
}

复杂度：时间 O(n)，空间 O(1)。

关键点：虚拟头结点统一处理；注意指针移动顺序。

25. K 个一组翻转链表

题目：每 K 个节点一组翻转，不足 K 个保持原样。

核心思路：先检查剩余节点数是否 >= K，然后调用反转子函数，并连接前后部分。

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    ListNode tail = head;
    for (int i = 0; i < k; i++) {
        if (tail == null) return head;
        tail = tail.next;
    }
    ListNode newHead = reverse(head, tail);
    head.next = reverseKGroup(tail, k);
    return newHead;
}
private ListNode reverse(ListNode head, ListNode tail) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != tail) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

复杂度：时间 O(n)，空间 O(1) 或递归栈 O(n/k)。

关键点：先定位当前组的尾部（tail），翻转区间为 [head, tail)。

二、双指针 / 快慢指针

141. 环形链表

题目：判断链表是否有环。

核心思路：快慢指针，快指针每次两步，慢指针一步，若有环则相遇。

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode slow = head, 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(1)。

142. 环形链表 II

题目：返回环的入口节点，无环返回 null。

核心思路：快慢指针相遇后，将慢指针重置到头，快指针在相遇点，两者同步走，再次相遇点即为环入口。

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

复杂度：时间 O(n)，空间 O(1)。

160. 相交链表

题目：找到两个链表相交的起始节点，不相交返回 null。

核心思路：双指针分别从两个链表头走，走完自己的链表后切换到对方链表，若相交则在第二次遍历时相遇。

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

复杂度：时间 O(m+n)，空间 O(1)。

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

题目：删除链表的倒数第 n 个节点，并返回头结点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

复杂度：时间 O(n)，空间 O(1)。

关键点：使用虚拟头结点方便删除头结点；快指针先走 n+1 步，使 slow 指向待删节点的前驱。

三、合并与加法

21. 合并两个有序链表 

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    cur.next = (list1 != null) ? list1 : list2;
    return dummy.next;
}

复杂度：时间 O(m+n)，空间 O(1)。

2. 两数相加

题目：两个非空链表表示非负整数（逆序存储），求它们的和并逆序返回。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        carry = sum / 10;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
    }
    return dummy.next;
}

复杂度：时间 O(max(m,n))，空间 O(max(m,n))（输出链表）。

23. 合并 K 个升序链表

核心思路：优先队列（小顶堆）每次取出最小节点接入。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
    for (ListNode node : lists) if (node != null) pq.offer(node);
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        cur.next = node;
        cur = cur.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

复杂度：时间 O(N log K)，空间 O(K)。

四、复杂链表操作

138. 随机链表的复制

核心思路：三步法（原地复制）：

  1. 在每个原节点后插入一个复制节点。
  2. 设置复制节点的 random 指针：copy.random = original.random.next。
  3. 分离原链表和复制链表。
public Node copyRandomList(Node head) {
    if (head == null) return null;
    Node cur = head;
    while (cur != null) {
        Node copy = new Node(cur.val);
        copy.next = cur.next;
        cur.next = copy;
        cur = copy.next;
    }
    cur = head;
    while (cur != null) {
        if (cur.random != null)
            cur.next.random = cur.random.next;
        cur = cur.next.next;
    }
    Node newHead = head.next;
    cur = head;
    while (cur != null) {
        Node copy = cur.next;
        cur.next = copy.next;
        cur = cur.next;
        if (cur != null) copy.next = cur.next;
    }
    return newHead;
}

复杂度：时间 O(n)，空间 O(1)（除输出外）。

148. 排序链表

核心思路：自底向上归并排序（迭代），先统计长度，然后按步长 1,2,4… 合并。

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    int len = 0;
    ListNode cur = head;
    while (cur != null) { len++; cur = cur.next; }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    for (int step = 1; step < len; step <<= 1) {
        ListNode prev = dummy;
        cur = dummy.next;
        while (cur != null) {
            ListNode left = cur;
            ListNode right = split(left, step);
            cur = split(right, step);
            prev.next = mergeTwoLists(left, right);
            while (prev.next != null) prev = prev.next;
        }
    }
    return dummy.next;
}
private ListNode split(ListNode head, int step) {
    if (head == null) return null;
    for (int i = 1; head.next != null && i < step; i++) head = head.next;
    ListNode right = head.next;
    head.next = null;
    return right;
}

复杂度：时间 O(n log n)，空间 O(1)。

五、设计类

146. LRU 缓存

题目：实现 LRU（最近最少使用）缓存，get 和 put 必须 O(1)。

核心思路：使用双向链表维护访问顺序（头部为最近使用），配合哈希表存储 key 到节点的映射。

class LRUCache {
    class DLinkedNode {
        int key, value;
        DLinkedNode prev, next;
        DLinkedNode(int k, int v) { key = k; value = v; }
    }
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size, capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new DLinkedNode(0, 0);
        tail = new DLinkedNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                DLinkedNode removed = removeTail();
                cache.remove(removed.key);
                size--;
            }
        }
    }
    // 省略双向链表操作方法：addToHead, removeNode, moveToHead, removeTail
}

复杂度：所有操作 O(1)，空间 O(capacity)。

十四题对比与总结

题目 技巧分类 时间复杂度 空间复杂度 核心要点
206 反转链表 基础反转 O(n) O(1) 三指针迭代
234 回文链表 反转 + 快慢指针 O(n) O(1) 找中点，反转后半
24 两两交换 交换操作 O(n) O(1) 虚拟头，三指针
25 K 组翻转 递归/迭代反转 O(n) O(1)/O(k) 先判长度，再反转区间
141 环检测 快慢指针 O(n) O(1) 同步移动检测相遇
142 环入口 快慢指针 O(n) O(1) 相遇后重置步调
160 相交链表 双指针 O(m+n) O(1) 互换路径长度
19 删除倒数 N 快慢指针 O(n) O(1) 虚拟头，先走 N+1
21 合并两链表 归并 O(m+n) O(1) 虚拟头，逐次选择
2 两数相加 模拟加法 O(n) O(n) 进位处理
23 合并 K 链表 优先队列/分治 O(N log K) O(K) 堆维护当前最小
138 随机复制 原地复制 O(n) O(1) 三步法：插、改、拆
148 排序链表 归并排序（迭代） O(n log n) O(1) 自底向上合并
146 LRU 哈希表+双向链表 O(1) O(capacity) 双向链表移动节点

总结心法：

  • 遇到链表题，优先考虑是否需要虚拟头结点（dummy）。
  • 涉及位置或距离，尝试快慢指针或双指针。
  • 需要反转或重组，考虑迭代三指针或递归。
  • 需要随机访问或快速查找，可借助哈希表。
  • 排序等复杂操作，归并排序是链表天然适合的算法。
© 2026 奇伏禾

🤖