第1章：链表的那些“相交”与“反转”戏码

1.1 判断两个链表是否相交（字节跳动、货拉拉）

问题背景：

在面试中，判断两个单链表是否相交是个经典题目，常被字节、货拉拉等公司拿来考察你的链表操作能力。相交的意思是，两个链表在某个节点开始共享相同的节点。难点在于如何高效判断，并且还能优化性能。

思路拆解：

• 双指针法（优雅且高效）：想象两个链表像两条绳子，可能在某处“打了个结”。我们可以通过计算长度差，让长链表先“走几步”，然后同步遍历，判断是否相遇。这种方法直观，空间复杂度低。步骤：遍历两个链表，分别计算长度 lenA 和 lenB。让长链表的指针先走 |lenA - lenB| 步，抹平长度差。两个指针同步前进，比较是否指向同一节点。如果走到末尾（null）还没相遇，说明不相交。
• 哈希表法（快速但占空间）：如果你追求速度，可以用哈希表存储一个链表的节点，遍历另一个链表时检查节点是否在哈希表中。找到即相交，没找到就不相交。注意：哈希表法虽然查找快，但需要额外空间，面试时要和面试官确认空间复杂度要求！

代码实现（双指针法）：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class LinkedListIntersection {
    public boolean isIntersect(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return false;

        // 计算长度
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        // 抹平长度差
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }

        // 同步遍历，检查是否相交
        while (headA != null && headB != null) {
            if (headA == headB) return true;
            headA = headA.next;
            headB = headB.next;
        }
        return false;
    }

    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public static void main(String[] args) {
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        ListNode intersect = new ListNode(4);
        headA.next.next.next = intersect;
        headA.next.next.next.next = new ListNode(5);

        ListNode headB = new ListNode(6);
        headB.next = new ListNode(7);
        headB.next.next = intersect;

        LinkedListIntersection solution = new LinkedListIntersection();
        System.out.println("相交？ " + solution.isIntersect(headA, headB)); // 输出 true
    }
}

优化技巧：

• 双指针的巧妙变体：如果不想单独算长度，可以用“环形追逐”思路：两个指针分别从 headA 和 headB 出发，遍历到末尾后切换到另一个链表继续走。如果相交，指针总会相遇；如果不相交，指针会同时到达 null。时间复杂度仍为 O(m+n)，但代码更简洁。
• 哈希表优化：如果用哈希表，优先用 HashSet，因为它只存储节点引用，空间复杂度为 O(min(m,n))。注意，哈希表法在链表很长时可能更快，但内存占用要权衡。

时间复杂度：双指针法 O(m+n)，哈希表法平均 O(m+n)，最坏 O(m+n)。

空间复杂度：双指针法 O(1)，哈希表法 O(min(m,n))。

面试Tips：

• 面试官可能追问：如果链表有环怎么办？双指针法依然适用，但哈希表法需要小心处理环的情况。
• 实际编码时，记得处理空链表的边界条件，避免空指针异常！

1.2 单链表反转（贝壳）

问题背景：

单链表反转是大厂面试的“常驻嘉宾”，贝壳、字节等公司尤其爱考。要求在 O(1) 空间复杂度下，将链表的指向全部反转，比如 1->2->3 变成 3->2->1。

思路拆解：

• 迭代法（直观且节省空间）：用三个指针：prev（前节点）、curr（当前节点）、next（下一节点）。每次让 curr.next 指向 prev，然后三指针一起后移。步骤：初始化 prev = null，curr = head。保存 next = curr.next。将 curr.next 指向 prev。移动 prev = curr，curr = next，继续循环。
• 递归法（优雅但需栈空间）：递归到链表末尾，从最后一个节点开始反转指向，逐步回溯调整指针。

代码实现（迭代法）：

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

public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next; // 保存下一节点
            curr.next = prev;         // 反转指针
            prev = curr;              // 前节点后移
            curr = next;              // 当前节点后移
        }
        return prev; // 新头节点
    }

    public void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ReverseLinkedList solution = new ReverseLinkedList();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        System.out.println("原链表：");
        solution.printList(head);

        ListNode reversed = solution.reverseList(head);
        System.out.println("反转后：");
        solution.printList(reversed);
    }
}

优化技巧：

• 边界处理：空链表或单节点链表直接返回，减少不必要循环。
• 递归写法：如果面试官要求递归，可以展示递归解法，但要说明递归会用 O(n) 栈空间，不如迭代法省空间。
• 扩展问题：面试官可能问“反转前K个节点”或“反转指定区间”，可以用类似逻辑，记录反转段的前后节点，重新连接。

时间复杂度：O(n)，遍历一次链表。

空间复杂度：O(1)（迭代法），O(n)（递归法）。

面试Tips：

• 写代码时，画个简单的链表图，手动推演指针变化，能避免逻辑错误。
• 如果面试官要求返回新头节点，记得返回 prev，因为它指向反转后的头！

1.3 链表判环与找入口（新浪）

问题背景：

链表判环和找环入口是新浪、字节等公司常考的进阶题。不仅要判断链表是否有环，还要精确找到环的入口节点，考察你对快慢指针的掌握。

思路拆解：

• 判环（快慢指针）：用两个指针，慢指针走一步，快指针走两步。如果链表有环，它们一定会相遇；如果无环，快指针会先到 null。
• 找入口：快慢指针相遇后，将慢指针重置到头节点，然后两者以相同速度（一步）移动，再次相遇的节点就是环入口。原理：假设头到入口距离为 a，入口到相遇点距离为 b，环剩余部分为 c。快慢指针相遇时，慢指针走了 a+b，快指针走了 2(a+b)。通过数学推导，第二次相遇必在入口。

代码实现：

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

public class LinkedListCycle {
    // 判断是否有环
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    // 找环入口
    public ListNode findCycleEntry(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;
    }

    public static void main(String[] args) {
        LinkedListCycle solution = new LinkedListCycle();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 环入口为node2

        System.out.println("有环？ " + solution.hasCycle(node1)); // true
        ListNode entry = solution.findCycleEntry(node1);
        System.out.println("环入口值：" + (entry != null ? entry.val : "无环")); // 2
    }
}

优化技巧：

• 边界检查：优先判断空链表或单节点，节省时间。
• 数学推导：面试时如果被问到原理，简单解释快慢指针的数学关系（2(a+b) = a+b+c+b），能加分。
• 扩展问题：如果要求返回环长度，可以在快慢指针相遇后继续走，统计循环次数。

时间复杂度：O(n)，快慢指针遍历一次，找入口再遍历一次。

空间复杂度：O(1)，仅用常数空间。

面试Tips：

• 画图是王道！用图展示快慢指针的移动和相遇，能让面试官直观理解你的思路。
• 如果链表超长，面试官可能问如何优化，提示：快慢指针已经是最佳方案！

1.4 合并两个有序链表（字节跳动、货拉拉）

问题背景：

合并两个有序链表是链表操作的经典题，字节、货拉拉常考。要求将两个升序链表合并成一个升序链表，考察指针操作。

思路拆解：

• 核心逻辑：用双指针比较链表节点，构建新链表。步骤：创建虚拟头节点（dummy）简化边界处理。比较两链表当前节点，取较小者接到结果链表，移动指针。处理剩余节点，直接接到结果尾部。

代码实现：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeSortedListNodes {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = l1 != null ? l1 : l2;

        return dummy.next;
    }

    public void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MergeSortedListNodes solution = new MergeSortedListNodes();
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        System.out.print("合并后：");
        ListNode merged = solution.mergeTwoLists(l1, l2);
        solution.printList(merged);
    }
}

优化技巧：

• 虚拟头节点：用dummy简化代码，避免单独处理头节点。
• 递归写法：可用递归合并，代码更简洁但栈空间为 O(n+m)。
• 原地合并：若允许修改原链表，可直接调整指针，节省空间。

时间复杂度：O(n + m)，遍历两链表。

空间复杂度：O(1)（迭代法），递归法为 O(n+m)。

面试Tips：

• 画出链表合并过程，标注dummy和current指针，能直观展示逻辑。
• 如果面试官问递归解法，展示后说明空间复杂度差异。

第2章：排序算法的“手撕”盛宴

2.1 冒泡排序（美团）

问题背景：

冒泡排序简单粗暴，是美团等公司考察基本功的常考题。虽然实际开发中很少用，但它能检验你对循环和交换逻辑的熟练度。

思路拆解：

• 核心逻辑：像气泡一样，把最大（或最小）元素逐步“冒”到数组一端。步骤：外层循环控制轮数，每轮确定一个最大元素。内层循环比较相邻元素，若前者大于后者，交换。优化：如果某轮没发生交换，说明数组已有序，提前退出。

代码实现：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // 提前退出
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        System.out.print("排序前：");
        for (int num : arr) System.out.print(num + " ");
        bubbleSort(arr);
        System.out.print("\n排序后：");
        for (int num : arr) System.out.print(num + " ");
    }
}

优化技巧：

• 提前终止：swapped 标记是关键，能将最好情况优化到 O(n)。
• 双向冒泡：面试官可能问“鸡尾酒排序”（双向冒泡），可以正反两方向冒泡，减少轮次。

时间复杂度：最好 O(n)，最坏/平均 O(n²)。

空间复杂度：O(1)，原地排序。

面试Tips：

• 写冒泡排序时，注意循环边界，避免越界。
• 如果面试官要求优化，提到 swapped 标志和双向冒泡，能展现你的深度！

2.2 快速排序（作业帮）

问题背景：

快速排序（Quick Sort）是大厂面试的“宠儿”，作业帮、字节等公司常考。它基于分治法，速度快，效率高，但实现细节容易出错，面试官爱看你能否写得又快又准。

思路拆解：

• 核心逻辑：选一个基准（pivot），将数组分成“小于pivot”和“大于pivot”两部分，递归处理子数组。步骤：选择pivot（常见选择：首元素、末元素、随机或中间值）。分区（partition）：通过双指针调整数组，让小于pivot的元素在左边，大于pivot的在右边，pivot归位。递归排序左右子数组。
• 关键点：分区操作要高效，pivot选择影响性能（最坏情况是数组已排序，退化到O(n²)）。

代码实现：

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSortHelper(arr, 0, arr.length - 1);
    }

    private static void quickSortHelper(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSortHelper(arr, left, pivotIndex - 1);
            quickSortHelper(arr, pivotIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];