LeetCode 热题 100 链表篇｜Java 通关全攻略：从基础到进阶的 20 道核心题解（附完整思路与代码）

一、链表刷题的 "三重境界"：从指针恐惧到模式化解题

作为从前端转后端的程序员，链表曾是我面试路上的 "拦路虎"。最初面对ListNode总是陷入：

• 指针断裂：修改.next 时忘记保存后续节点
• 边界陷阱：头节点 / 尾节点处理遗漏
• 逻辑混乱：多指针移动时陷入指针指向迷宫

但刷完 Hot 100 链表题后，我发现所有问题都逃不过四大解题模式：双指针定位、虚拟头节点统一逻辑、递归拆解问题、快慢指针数学模型。本文将通过 20 道经典题目，带你建立链表解题的 "肌肉记忆"。

二、链表解题的四大核心武器

三、基础必刷题：建立链表操作的底层认知

1. 反转链表（#206）- 指针操作的 "Hello World"

心路历程：第一次实现时用了 3 个临时变量，代码冗长到怀疑人生，后来发现双指针可以优雅解决。

// 迭代法（时间O(n) 空间O(1)）
public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;  // 先保存下一个节点
        curr.next = prev;                // 反转指针
        prev = curr;                     // 双指针后移
        curr = nextTemp;
    }
    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;
}

关键点：迭代法像 "穿珠子"，递归法像 "翻绳子"，两种思路都要掌握。

2. 合并两个有序链表（#21）- 虚拟头节点的经典应用

踩坑记录：第一次没用 dummy 节点，写了 10 行边界判断代码，惨不忍睹。

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;  // 跳过虚拟头节点
}

技巧升华：dummy 节点的本质是 "用空间换逻辑简化"，后续很多题目都能用到。

3. 环形链表（#141）- 快慢指针的数学魅力

数学推导：设环前长度为 a，环长为 b，快慢指针相遇时：

• 慢指针走了 a + k*b
• 快指针走了 a + m*b
• 快指针速度是慢指针 2 倍 → 2 (a + kb) = a + mb → a = (m-2k)b - kb → a = (m-2k-1)b + (b -kb)

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

扩展思考：如何找到环的入口？（见 #142 环形链表 II）

4. 删除链表的倒数第 N 个节点（#19）- 双指针的距离魔法

核心思路：让快指针先走 n 步，然后快慢指针同步走，当快指针到末尾时，慢指针恰好在目标节点前。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);  // 虚拟头节点防头删
    ListNode first = dummy, second = dummy;
    
    // 快指针先走n+1步（包括虚拟节点）
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    
    // 同步移动
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    
    // 删除节点
    second.next = second.next.next;
    return dummy.next;
}

易错点：必须考虑删除头节点的情况，dummy 节点是关键。

5. 链表的中间节点（#876）- 快慢指针找中点

巧妙之处：快指针每次走两步，慢指针走一步，快指针到末尾时，慢指针恰好在中点。

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

变种应用：若链表长度为偶数，返回第二个中点（如 1->2->3->4 返回 3）

四、进阶提升题：指针操作的灵活运用

6. 相交链表（#160）- 双指针的 "终点相遇" 策略

核心思想：让两指针从各自链表走到末尾后，转向走另一个链表，相遇点即为交点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    
    // 当pA/pB走到末尾时，转向另一个链表
    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next;
        pB = (pB == null) ? headA : pB.next;
    }
    return pA;
}

数学证明：设 A 链长 a，B 链长 b，交点前长度 c，则 a + b - c = b + a - c，两指针走的总距离相等。

7. 环形链表 II（#142）- 找环入口的数学推导

结论：快慢指针相遇后，让慢指针从起点出发，快指针从相遇点出发，速度都为 1，相遇点即为环入口。

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) return null;
    ListNode slow = head, fast = head;
    boolean hasCycle = false;
    
    // 先找相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    if (!hasCycle) return null;
    
    // 找环入口
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

推导过程：相遇时慢指针走了 a + kb，快指针走了 a + mb，且快指针走了 2 倍距离，解得 a = (m-2k)b -kb = (m-2k-1)b + (b -kb)，即 a = (m-2k-1)b + (b -kb)，所以从起点和相遇点同时走，会在环入口相遇。

8. 排序链表（#148）- 归并排序的链表实现

核心步骤：

1. 找中点（快慢指针）
2. 分割链表
3. 递归排序
4. 合并有序链表

public ListNode sortList(ListNode head) {
    // 边界条件
    if (head == null || head.next == null) return head;
    
    // 找中点
    ListNode mid = getMiddle(head);
    ListNode rightHead = mid.next;
    mid.next = null;  // 分割链表
    
    // 递归排序
    ListNode left = sortList(head);
    ListNode right = sortList(rightHead);
    
    // 合并有序链表
    return mergeTwoLists(left, right);
}

// 找中点辅助函数
private ListNode getMiddle(ListNode head) {
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

复杂度分析：时间 O (nlogn)，空间 O (logn)（递归栈）

9. 分隔链表（#86）- 根据值分割链表

双指针思想：维护两个链表，分别存小于 x 和大于等于 x 的节点

public ListNode partition(ListNode head, int x) {
    if (head == null || head.next == null) return head;
    
    ListNode less = new ListNode(0);  // 小于x的虚拟头
    ListNode more = new ListNode(0);  // 大于等于x的虚拟头
    ListNode l = less, m = more;
    
    // 遍历分割
    while (head != null) {
        if (head.val < x) {
            l.next = head;
            l = l.next;
        } else {
            m.next = head;
            m = m.next;
        }
        head = head.next;
    }
    
    // 连接两部分，注意尾节点置null
    m.next = null;
    l.next = more.next;
    return less.next;
}

关键点：尾节点必须置 null，否则可能形成环。

10. 复制带随机指针的链表（#138）- 哈希表与原地复制

解法一：哈希表映射（简单直观）

public Node copyRandomList(Node head) {
    if (head == null) return null;
    Map<Node, Node> map = new HashMap<>();
    
    // 第一步：复制节点并建立映射
    Node curr = head;
    while (curr != null) {
        map.put(curr, new Node(curr.val));
        curr = curr.next;
    }
    
    // 第二步：复制next和random指针
    curr = head;
    while (curr != null) {
        map.get(curr).next = map.get(curr.next);
        map.get(curr).random = map.get(curr.random);
        curr = curr.next;
    }
    return map.get(head);
}

解法二：原地复制（空间优化）

public Node copyRandomList(Node head) {
    if (head == null) return null;
    
    // 1. 在原节点后复制新节点
    Node curr = head;
    while (curr != null) {
        Node copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }
    
    // 2. 复制random指针
    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    
    // 3. 拆分链表
    Node dummy = new Node(0);
    Node copyCurr = dummy;
    curr = head;
    
    while (curr != null) {
        // 保存原链表下一个节点
        Node next = curr.next.next;
        
        // 取下复制节点
        copyCurr.next = curr.next;
        copyCurr = copyCurr.next;
        
        // 恢复原链表
        curr.next = next;
        curr = next;
    }
    return dummy.next;
}

对比：哈希表解法时间 O (n) 空间 O (n)，原地复制时间 O (n) 空间 O (1)

五、高阶挑战题：链表与其他数据结构的结合

11. 两数相加（#2）- 链表模拟大数加法

核心逻辑：

• 逆序存储数字（个位在前）
• 模拟手工加法，记录进位
• 处理长度不等的链表

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

扩展思考：如果数字是顺序存储的（高位在前），如何处理？

12. 回文链表（#234）- 快慢指针 + 栈 / 反转

解法一：快慢指针找中点 + 反转后半段（推荐）

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    
    // 1. 找中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. 反转后半段
    ListNode secondHalf = reverseList(slow.next);
    slow.next = null;  // 断开前半段
    
    // 3. 比较两段
    ListNode p1 = head, p2 = secondHalf;
    boolean isPalindrome = true;
    while (p2 != null) {
        if (p1.val != p2.val) {
            isPalindrome = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    
    // 4. 恢复链表（可选）
    slow.next = reverseList(secondHalf);
    return isPalindrome;
}

// 反转链表辅助函数
private ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

解法二：栈存储所有节点（空间 O (n)）

13. 奇偶链表（#328）- 双指针分组重组

思路：维护奇数链表和偶数链表，最后连接

public ListNode oddEvenList(ListNode head) {
    if (head == null || head.next == null) return head;
    
    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;
    return head;
}

关键点：偶数链表的最后一个节点可能为空，需正确判断终止条件。

14. 重新排列链表（#143）- 找中点 + 反转 + 合并

三步曲：

1. 找中点
2. 反转后半段
3. 合并前后两段

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    
    // 1. 找中点
    ListNode mid = getMiddle(head);
    ListNode secondHalf = mid.next;
    mid.next = null;  // 分割链表
    
    // 2. 反转后半段
    secondHalf = reverseList(secondHalf);
    
    // 3. 合并两段
    mergeAlternately(head, secondHalf);
}

// 合并两段链表（交替插入）
private void mergeAlternately(ListNode l1, ListNode l2) {
    while (l1 != null && l2 != null) {
        ListNode next1 = l1.next;
        ListNode next2 = l2.next;
        
        l1.next = l2;
        l1 = next1;
        
        l2.next = l1;
        l2 = next2;
    }
}

注意：此操作会修改原链表，需谨慎使用。

15. 链表组件（#817）- 哈希表标记节点

核心思想：用哈希表记录目标节点，遍历链表时统计连续组件

public int numComponents(ListNode head, int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) set.add(num);
    
    int count = 0;
    boolean inComponent = false;
    
    while (head != null) {
        if (set.contains(head.val)) {
            if (!inComponent) {
                count++;
                inComponent = true;
            }
        } else {
            inComponent = false;
        }
        head = head.next;
    }
    return count;
}

复杂度：时间 O (n+m)，n 为链表长度，m 为 nums 长度

六、我的链表刷题心法：从 "踩坑" 到 "封神"

1. 入门三剑客（必刷）

   • #206 反转链表：掌握指针基本操作
   • #21 合并链表：学会虚拟头节点用法
   • #141 环形链表：理解快慢指针数学原理

2. 进阶三关（突破点）

   • #19 删除倒数第 N 节点：双指针距离计算
   • #142 环形链表 II：数学推导环入口
   • #148 排序链表：链表与递归结合

3. 避坑指南（血的教训）

   • ✅ 所有链表操作前先判空：if (head == null) return
   • ✅ 修改next前先保存后续节点：ListNode nextTemp = curr.next
   • ✅ 涉及头节点修改时用虚拟头节点：ListNode dummy = new ListNode(0)
   • ✅ 多指针操作时画图辅助：用→表示 next 指针

4. 调试神器

   // 打印链表辅助函数
   public void printList(ListNode head) {
       while (head != null) {
           System.out.print(head.val + "→");
           head = head.next;
       }
       System.out.println("null");
   }
   

七、结语：链表是算法的 "试金石"

刷完这 20 道题，你会发现：

• 链表操作本质是指针的舞蹈，关键在于掌握 "移动 - 修改 - 保存" 的节奏
• 90% 的链表题都可以用双指针 + 虚拟头节点框架解决
• 递归解法的核心是定义子问题，而非陷入具体指针操作

下期预告：《LeetCode 热题 100 二叉树篇｜从递归三定律到层序遍历的全攻略》，关注我获取最新更新！

（原创不易，转载请注明出处，让我们在刷题路上共同进步！）

统计：

本文涵盖 LeetCode Hot 100 中15 道核心链表题，覆盖链表反转、合并、删除、检测环、排序、回文判断等90% 以上的链表考点，适合从入门到进阶的程序员系统学习。

互动话题：

你在链表题中遇到的最棘手问题是什么？或者哪道题的解法让你拍案叫绝？评论区分享你的刷题故事吧！