一、链表操作：从入门到实战

链表这玩意儿，说实话是面试里的常客。我当年刚入行时，总觉得链表操作就是背模板，直到在一次线上排查内存泄漏时，才发现自己对链表的理解有多浅。今天咱们就把链表操作的核心套路捋一遍。

1.1 链表反转——最基础的“翻盘”操作

链表反转，说白了就是把箭头方向全部调个头。我习惯用迭代法，因为它空间复杂度是 O(1)，而且逻辑清晰。

// 反转单链表（迭代法）
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;
}

1.2 快慢指针——链表里的“双人舞”

快慢指针，一个走两步，一个走一步。你想想看，如果链表有环，快指针迟早会追上慢指针。这个套路在环形链表检测、找中点、找倒数第K个节点时特别好用。

// 判断链表是否有环
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;
}

1.3 合并有序链表——归并思想在链表上的体现

合并两个有序链表，其实就是归并排序的链表版本。我个人习惯用递归，代码简洁，但要注意递归深度。

// 合并两个有序链表（递归版）
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

1.4 经典例题精讲

环形链表 II——找到环的入口

这道题比判断是否有环多一步：找到环的入口。我记得第一次做这题时，被数学推导绕晕了。其实核心就一句话：相遇后，让一个指针从头开始，另一个从相遇点开始，都走一步，再次相遇就是入口。

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) { // 相遇了
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr; // 环的入口
        }
    }
    return null;
}

相交链表——找两个链表的交点

这道题的经典解法是：两个指针分别从两个链表头出发，走到末尾后跳到另一个链表头继续走。如果相交，它们会在交点相遇。为什么？因为走过的路程相同。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next;
        pB = (pB == null) ? headA : pB.next;
    }
    return pA;
}

1.5 知识体系总览

下面这张图，是我自己梳理的链表操作知识体系。你可以把它当作复习地图。

1.6 避坑指南

• 空指针检查： 操作链表前，一定要检查 head 是否为 null。我曾经在线上环境因为没判空，导致整个服务挂了。
• 边界条件： 反转时注意头尾节点，合并时注意其中一个链表先走完的情况。
• 循环引用： 反转链表时，如果忘记断开原引用，可能会造成循环引用，导致内存泄漏。
• 快慢指针初始化： 有些题目要求 slow 和 fast 都从 head 开始，有些要求 fast 从 head.next 开始。具体看题目要求，别搞混了。

---