双指针秒杀 6 大链表常考高频题

链表相关的问题，90% 都可以用 双指针技巧（快慢指针、左右指针） 优雅解决。

1. 合并两个有序链表 (LeetCode 21)

这是最基础的链表算法，核心就在于使用一个 dummy 虚拟头节点，避免处理头节点为空的边界条件。

Java 解法代码

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = list1, p2 = list2;
        
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null) p.next = p1;
        if (p2 != null) p.next = p2;
        
        return dummy.next;
    }
}

Python3 解法代码

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        p = dummy
        p1, p2 = list1, list2
        while p1 and p2:
            if p1.val < p2.val:
                p.next = p1
                p1 = p1.next
            else:
                p.next = p2
                p2 = p2.next
            p = p.next
        if p1: p.next = p1
        if p2: p.next = p2
        return dummy.next

2. 快慢指针寻找链表中点 (LeetCode 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;
}

3. 判断链表是否有环 (LeetCode 141)

同样利用快慢指针，如果有环，快指针最终一定会追上慢指针：

public boolean hasCycle(ListNode head) {
    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;
}