Day 3 - 链表专题

📅 日期：2026年1月10日
🎯 主题：链表基础 + 指针操作

今日题目

题目1：反转链表 (Reverse Linked List)

难度：⭐ 简单

链接：LeetCode 206. 反转链表

题目描述

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]

输入：head = []
输出：[]

解题思路

方法一：迭代法（双指针） ✅ 推荐

核心思想：

1. 使用两个指针：prev（前一个节点）和 curr（当前节点）
2. 遍历链表，每次将当前节点的 next 指向前一个节点
3. 然后 prev 和 curr 都向前移动一位
4. 直到 curr 为 null，此时 prev 就是新的头节点

关键步骤：

初始：null -> 1 -> 2 -> 3 -> 4 -> 5 -> null
      prev  curr

第1步：null <- 1    2 -> 3 -> 4 -> 5 -> null
            prev  curr

第2步：null <- 1 <- 2    3 -> 4 -> 5 -> null
                 prev  curr

...继续直到 curr 为 null

方法二：递归法

核心思想：

1. 递归到链表末尾
2. 从后往前反转每个节点
3. 返回新的头节点

代码实现

方法一：迭代法（双指针）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    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;  // prev 是新的头节点
    }
}

方法二：递归法

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归终止条件：空链表或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        
        // 递归反转后面的链表
        ListNode newHead = reverseList(head.next);
        
        // 反转当前节点
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
}

复杂度分析

• 时间复杂度：O(n)，需要遍历整个链表
• 空间复杂度：
  • 迭代法：O(1)，只使用常数额外空间
  • 递归法：O(n)，递归调用栈的深度为 n

---

题目2：合并两个有序链表 (Merge Two Sorted Lists)

难度：⭐ 简单

链接：LeetCode 21. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

解题思路

方法一：迭代法（双指针） ✅ 推荐

核心思想：

1. 创建一个虚拟头节点 dummy，简化边界处理
2. 使用指针 curr 指向当前合并后的链表末尾
3. 比较两个链表的当前节点值，将较小的节点接到 curr 后面
4. 移动对应的指针和 curr 指针
5. 当其中一个链表遍历完后，将另一个链表的剩余部分接到结果链表后面

关键点：

• 使用虚拟头节点可以避免处理空链表的特殊情况
• 两个指针分别遍历两个链表，每次选择较小的节点

方法二：递归法

核心思想：

1. 比较两个链表的头节点
2. 选择较小的节点作为结果的头节点
3. 递归合并剩余部分
4. 将结果连接到选中的头节点后面

代码实现

方法一：迭代法（双指针）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建虚拟头节点，简化边界处理
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        // 同时遍历两个链表
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        
        // 将剩余部分接到结果链表后面
        curr.next = (list1 != null) ? list1 : list2;
        
        return dummy.next;  // 返回真正的头节点
    }
}

方法二：递归法

class Solution {
    public ListNode mergeTwoLists(ListNode list1, 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)，其中 n 和 m 分别是两个链表的长度
• 空间复杂度：
  • 迭代法：O(1)，只使用常数额外空间
  • 递归法：O(n + m)，递归调用栈的深度

---

今日总结

学到了什么？

1. 链表反转技巧：使用双指针（prev 和 curr）逐个反转节点
2. 虚拟头节点：简化边界处理，避免空指针异常
3. 双指针合并：同时遍历两个有序链表，选择较小的节点
4. 递归思维：将问题分解为子问题，递归求解

关键技巧

技巧	适用场景	时间复杂度
双指针反转	链表反转、部分反转	O(n)
虚拟头节点	简化边界处理、统一操作	O(1) 额外空间
双指针合并	合并有序链表/数组	O(n + m)
递归	链表操作、树操作	O(n) 空间（调用栈）

链表操作要点

1. 指针移动顺序：

   • 先保存 next 指针
   • 再修改当前节点的 next
   • 最后移动指针

2. 边界处理：

   • 空链表：head == null
   • 单节点：head.next == null
   • 使用虚拟头节点可以简化处理

3. 常见错误：

   • 忘记保存 next 指针导致链表断裂
   • 指针移动顺序错误
   • 边界条件处理不当

相似题目推荐

• 反转链表 II - 反转部分链表
• K 个一组翻转链表 - 分组反转
• 合并 K 个升序链表 - 合并多个有序链表
• 两数相加 - 链表相加

明日计划

• Day 4 链表进阶
• 练习：环形链表、删除链表的倒数第 N 个结点