链表实战：LeetCode Hot 100 经典题目深度解析

复杂度分析：

• 时间复杂度：O(N)，其中 N 是链表的长度。需要遍历链表一次。
• 空间复杂度：O(1)，只使用了几个指针变量，属于原地反转。

边界测试用例：

• 输入 NULL → 输出 NULL
• 输入 [1] → 输出 [1]

解法二：递归

思路解析： 递归的核心思想是'大事化小'。假设链表的后半部分已经被反转，我们只需要处理当前节点和它后面的节点。

1. 递归终止条件：head 为 NULL 或 head->next 为 NULL。
2. 递归调用 reverseList(head->next)，得到反转后的新头节点 newHead。
3. 将当前节点的下一个节点的 next 指向自己，即 head->next->next = head。
4. 将当前节点的 next 指向 NULL，防止链表成环。
5. 返回新头节点 newHead。

struct ListNode* reverseList(struct ListNode* head) {
    // 递归终止条件：空链表 或 只有一个节点
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // 递归调用，反转 head 之后的所有节点
    struct ListNode* newHead = reverseList(head->next);
    // 反转当前节点与下一个节点的指向
    head->next->next = head;
    head->next = NULL; // 防止链表成环，这一步是关键
    return newHead;
}

复杂度分析：

• 时间复杂度：O(N)，需要递归 N 次，遍历所有节点。
• 空间复杂度：O(N)，递归调用栈的深度为 N，最坏情况下链表退化为一条链。

解法对比：

题目二：环形链表 (LeetCode 141)

题目描述：给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 示例：输入 head = [3,2,0,-4], pos = 1 (链表尾部连接到第二个节点)，输出 true 难度：简单 考察频率：⭐⭐⭐⭐

解法：快慢指针（Floyd 判圈算法）

思路解析： 想象在环形跑道上跑步的场景：一个跑得快的运动员和一个跑得慢的运动员，如果跑道是环形的，快的运动员最终一定会追上慢的运动员；如果是直线跑道，快的运动员会先到达终点。

• 设置慢指针 slow：每次向后移动 1 步。
• 设置快指针 fast：每次向后移动 2 步。
• 有环情况：fast 指针会追上 slow 指针，此时 slow == fast。
• 无环情况：fast 指针会先到达链表末尾（fast == NULL 或 fast->next == NULL）。

bool hasCycle(struct ListNode* head) {
    // 处理空链表和单节点链表
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head->next; // 初始错开，避免直接相等
    
    while (slow != fast) {
        // 快指针到达终点，无环
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        slow = slow->next;      // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
    }
    // 快慢指针相遇，有环
    return true;
}

关键细节：

• 快指针初始化为 head->next，而不是 head，避免循环一开始就满足 slow == fast。
• 循环条件必须判断 fast 和 fast->next 是否为空，防止空指针访问。

复杂度分析：

• 时间复杂度：O(N)。有环时，快慢指针相遇时，慢指针走过的距离不会超过链表总长度；无环时，快指针遍历链表一次。
• 空间复杂度：O(1)，只使用了两个指针变量，无需额外空间。

拓展思路：哈希表法 可以使用哈希表存储访问过的节点，遍历链表时如果遇到重复节点则说明有环。但该方法空间复杂度为 O(N)，不如快慢指针法高效。

题目三：合并两个有序链表 (LeetCode 21)

题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入 l1 = [1,2,4], l2 = [1,3,4]，输出 [1,1,2,3,4,4] 难度：简单 考察频率：⭐⭐⭐⭐⭐

解法一：迭代（虚拟头节点）

思路解析： 这是一个典型的归并操作。直接操作两个链表的头节点会面临边界问题（比如某个链表为空），因此我们引入虚拟头节点 dummy，用 cur 指针构建新链表。

1. 创建虚拟头节点 dummy，cur 指针初始指向 dummy。
2. 循环比较两个链表的当前节点值，将较小值的节点连接到 cur 后面。
3. 移动对应链表的指针和 cur 指针。
4. 当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到 cur 后面。
5. 返回 dummy->next 作为新链表的头节点。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 创建虚拟头节点，简化边界处理
    struct ListNode dummy;
    dummy.next = NULL;
    struct 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 指针后移
    }
    // 连接剩余的节点
    cur->next = (list1 != NULL) ? list1 : list2;
    return dummy.next;
}

复杂度分析：

• 时间复杂度：O(N + M)，其中 N 和 M 分别是两个链表的长度，需要遍历所有节点。
• 空间复杂度：O(1)，只使用了虚拟头节点和几个指针，原地合并。

解法二：递归

思路解析： 递归的核心是每次选择两个链表中较小的头节点，然后递归合并剩余的部分。

1. 终止条件：如果 list1 为空，返回 list2；如果 list2 为空，返回 list1。
2. 比较 list1 和 list2 的头节点值，选择较小的作为当前节点。
3. 递归合并剩余的链表，并将结果连接到当前节点的后面。
4. 返回当前节点。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 终止条件：一个链表为空，返回另一个链表
    if (list1 == NULL) {
        return list2;
    }
    if (list2 == NULL) {
        return list1;
    }
    
    // 选择较小的节点作为当前节点
    if (list1->val < list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

复杂度分析：

• 时间复杂度：O(N + M)，需要递归合并所有节点。
• 空间复杂度：O(N + M)，递归调用栈的深度为两个链表的长度之和。

题目四：删除链表的倒数第 N 个结点 (LeetCode 19)

题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例：输入 head = [1,2,3,4,5], n = 2，输出 [1,2,3,5] 难度：中等 考察频率：⭐⭐⭐⭐⭐

解法：双指针（间隔法）

思路解析： 删除倒数第 n 个节点，关键是找到倒数第 n+1 个节点（目标节点的前驱节点）。使用双指针法可以在一次遍历中完成：

1. 创建虚拟头节点 dummy，指向 head，避免删除头节点的边界问题。
2. 定义快慢指针 fast 和 slow，初始都指向 dummy。
3. 先让 fast 指针向前移动 n+1 步，使 fast 和 slow 之间间隔 n 个节点。
4. 然后让 fast 和 slow 同时向前移动，直到 fast 指向 NULL。
5. 此时 slow 指向的就是倒数第 n+1 个节点，执行删除操作：slow->next = slow->next->next。
6. 返回 dummy->next。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // 创建虚拟头节点
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* fast = &dummy;
    struct ListNode* slow = &dummy;
    
    // fast 指针先走 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }
    
    // 快慢指针同时移动
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    // 删除倒数第 n 个节点
    struct ListNode* temp = slow->next; // 保存要删除的节点
    slow->next = slow->next->next;
    free(temp); // 释放内存，避免内存泄漏
    return dummy.next;
}

关键细节：

• 虚拟头节点是必须的，否则当 n 等于链表长度时，无法删除头节点。
• fast 指针需要移动 n+1 步，而不是 n 步，这样才能让 slow 停在目标节点的前驱。
• 删除节点后要释放内存，避免内存泄漏。

复杂度分析：

• 时间复杂度：O(N)，只需要遍历链表一次。
• 空间复杂度：O(1)，使用常数级别的额外空间。

三、总结与进阶

恭喜你完成了本次链表王者试炼！通过对这四道经典题目的深入剖析，你不仅巩固了链表的基础知识，更重要的是掌握了双指针、虚拟头节点、递归等高级解题技巧，并学会了从不同角度思考问题，分析算法的优劣。

你已掌握的核心能力

1. 算法思维：能够分析问题本质，选择最优的解题策略。
2. 编码能力：能够将解题思路转化为清晰、高效、健壮的代码。
3. 复杂度分析：能够评估算法的时间和空间效率，选择最优解。
4. 边界处理：能够考虑到各种特殊情况，写出鲁棒性强的代码。

后续挑战

这几道题目只是链表领域的冰山一角，想要成为真正的'链表王者'，还需要攻克以下进阶题目：

• K 个一组翻转链表 (LeetCode 25)：反转链表的进阶版，难度较大，面试高频硬核题。
• 相交链表 (LeetCode 160)：寻找两个链表的第一个公共节点，双指针法的巧妙应用。
• 复制带随机指针的链表 (LeetCode 138)：对链表和哈希表的综合考察，难度较高。
• 排序链表 (LeetCode 148)：要求 O(n log n) 时间复杂度和常数级空间复杂度，考验算法功底。

数据结构与算法的学习之路永无止境，没有捷径可走，唯有多敲代码、多画图、多思考，才能真正掌握其精髓。希望这个系列能成为你坚实的基石，祝你在未来的学习和面试中披荆斩棘，所向披靡！🚀