合并两个有序链表

1. 问题描述和示例

问题描述

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

示例

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

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

约束条件

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按非递减顺序排列

2. 核心难点分析

主要挑战

1. 指针操作复杂性：需要正确处理多个指针的移动和连接
2. 边界条件处理：空链表、单节点链表等特殊情况
3. 内存管理：避免创建不必要的新节点，直接重用原有节点
4. 链表遍历同步：两个链表长度可能不同，需要处理剩余节点

关键思路

• 利用链表已排序的特性，使用双指针技术
• 比较当前节点值，选择较小的节点加入结果链表
• 处理其中一个链表遍历完成后的剩余节点

3. 多种解法分析

解法一：递归法

思路：

• 比较两个链表头节点的值
• 选择较小的节点，递归处理剩余部分
• 递归终止条件：其中一个链表为空

优点：代码简洁，逻辑清晰 缺点：空间复杂度较高（递归栈）

解法二：迭代法

思路：

• 使用循环代替递归
• 维护当前指针，逐个比较和连接节点
• 处理剩余节点

优点：空间复杂度低 缺点：代码稍复杂

解法三：虚拟头节点法

思路：

• 创建虚拟头节点简化边界处理
• 使用迭代方式合并
• 返回虚拟头节点的下一个节点

优点：代码清晰，易于理解和实现 缺点：需要额外的虚拟节点

4. 详细代码实现

Java实现

递归法

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

public 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;
        }
    }
}

迭代法（虚拟头节点）

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建虚拟头节点
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        // 同时遍历两个链表
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        // 连接剩余节点
        current.next = (list1 != null) ? list1 : list2;
        
        return dummy.next;
    }
}

Python实现

递归法

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        # 递归终止条件
        if not list1:
            return list2
        if not list2:
            return list1
        
        # 比较当前节点值，选择较小的节点
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

迭代法（虚拟头节点）

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        # 创建虚拟头节点
        dummy = ListNode(0)
        current = dummy
        
        # 同时遍历两个链表
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        
        # 连接剩余节点
        current.next = list1 if list1 else list2
        
        return dummy.next

5. 复杂度分析

时间复杂度

• 递归法：O(m + n)，其中 m 和 n 分别是两个链表的长度
• 迭代法：O(m + n)，需要遍历两个链表的所有节点

空间复杂度

• 递归法：O(m + n)，递归调用栈的深度
• 迭代法：O(1)，只使用常数额外空间

性能对比

方法	时间复杂度	空间复杂度	代码复杂度	推荐度
递归法	O(m+n)	O(m+n)	低	⭐⭐⭐
迭代法	O(m+n)	O(1)	中	⭐⭐⭐⭐⭐

6. 边界情况处理

常见边界情况

1. 空链表处理

   if not list1: return list2
   if not list2: return list1
   

2. 单节点链表

   # 正常逻辑即可处理，无需特殊处理
   

3. 长度差异很大的链表

   # 使用剩余节点直接连接
   current.next = list1 if list1 else list2
   

4. 相同值节点

   # 保持稳定性，优先选择第一个链表的节点
   if list1.val <= list2.val:  # 注意使用 <= 而不是 <
   

测试用例

def test_merge_two_lists():
    solution = Solution()
    
    # 测试用例1：正常情况
    # l1: 1->2->4, l2: 1->3->4
    # 期望: 1->1->2->3->4->4
    
    # 测试用例2：空链表
    assert solution.mergeTwoLists(None, None) is None
    
    # 测试用例3：一个空链表
    # l1: None, l2: 1->2->3
    # 期望: 1->2->3
    
    # 测试用例4：单节点
    # l1: 1, l2: 2
    # 期望: 1->2
    
    print("所有测试用例通过！")

7. 相关变种问题

7.1 合并K个有序链表

LeetCode 23

def mergeKLists(self, lists):
    if not lists:
        return None
    
    # 分治法：两两合并
    while len(lists) > 1:
        merged_lists = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged_lists.append(self.mergeTwoLists(l1, l2))
        lists = merged_lists
    
    return lists[0]

7.2 链表排序

LeetCode 148

def sortList(self, head):
    if not head or not head.next:
        return head
    
    # 找到中点，分割链表
    mid = self.getMid(head)
    left = head
    right = mid.next
    mid.next = None
    
    # 递归排序
    left = self.sortList(left)
    right = self.sortList(right)
    
    # 合并有序链表
    return self.mergeTwoLists(left, right)

7.3 合并两个有序数组

LeetCode 88

• 类似思路，但操作数组而非链表
• 可以从后往前合并，避免额外空间

8. 性能优化技巧

8.1 减少不必要的比较

def mergeTwoLists(self, list1, list2):
    # 提前处理空链表情况
    if not list1: return list2
    if not list2: return list1
    
    # 确保 list1 指向较小的头节点
    if list1.val > list2.val:
        list1, list2 = list2, list1
    
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    current.next = list1 or list2
    return dummy.next

8.2 内存优化

# 避免创建新节点，直接重用原有节点
# 这是本题的标准做法，已经是最优的内存使用

8.3 批量处理优化

def mergeTwoListsOptimized(self, list1, list2):
    """针对大量相同值的优化版本"""
    if not list1: return list2
    if not list2: return list1
    
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            # 批量处理相同值的节点
            while list1 and list1.val <= list2.val:
                current.next = list1
                current = list1
                list1 = list1.next
        else:
            while list2 and list2.val < list1.val:
                current.next = list2
                current = list2
                list2 = list2.next
    
    current.next = list1 or list2
    return dummy.next

9. 实际应用场景

9.1 数据库查询结果合并

# 合并两个按时间排序的日志文件
def merge_log_files(log1, log2):
    """合并两个按时间戳排序的日志链表"""
    return mergeTwoLists(log1, log2)

9.2 分布式系统数据合并

# 合并来自不同服务器的有序数据
class DataMerger:
    def merge_server_data(self, server1_data, server2_data):
        """合并两个服务器返回的有序数据"""
        return self.mergeTwoLists(server1_data, server2_data)

9.3 实时数据流处理

# 合并两个实时数据流
class StreamMerger:
    def merge_streams(self, stream1, stream2):
        """实时合并两个有序数据流"""
        # 使用迭代法，适合流式处理
        pass

9.4 版本控制系统

# Git merge 操作的简化版本
class GitMerger:
    def merge_commits(self, branch1_commits, branch2_commits):
        """按时间戳合并两个分支的提交记录"""
        return self.mergeTwoLists(branch1_commits, branch2_commits)

10. 常见错误与调试

10.1 常见错误

1. 忘记处理空链表

   # 错误：没有检查空链表
   def mergeTwoLists(self, list1, list2):
       while list1 and list2:  # 如果一开始就有空链表会出错
           # ...
   
   # 正确：提前处理空链表
   def mergeTwoLists(self, list1, list2):
       if not list1: return list2
       if not list2: return list1
       # ...
   

2. 指针移动错误

   # 错误：忘记移动指针
   while list1 and list2:
       if list1.val <= list2.val:
           current.next = list1
           # 忘记移动 list1 指针
       # ...
   
   # 正确：记得移动指针
   while list1 and list2:
       if list1.val <= list2.val:
           current.next = list1
           list1 = list1.next  # 移动指针
       # ...
   

3. 忘记连接剩余节点

   # 错误：循环结束后没有处理剩余节点
   while list1 and list2:
       # 合并逻辑
   return dummy.next  # 可能丢失剩余节点
   
   # 正确：连接剩余节点
   while list1 and list2:
       # 合并逻辑
   current.next = list1 or list2  # 连接剩余节点
   return dummy.next
   

10.2 调试技巧

1. 打印链表状态

   def print_list(head, name="List"):
       """调试用：打印链表"""
       result = []
       current = head
       while current:
           result.append(current.val)
           current = current.next
       print(f"{name}: {result}")
   
   # 在关键位置添加调试信息
   def mergeTwoLists(self, list1, list2):
       print_list(list1, "Input List1")
       print_list(list2, "Input List2")
       
       # 合并逻辑...
       
       print_list(result, "Merged Result")
       return result
   

2. 断点调试

   def mergeTwoLists(self, list1, list2):
       dummy = ListNode(0)
       current = dummy
       
       while list1 and list2:
           # 在这里设置断点，观察指针状态
           if list1.val <= list2.val:
               current.next = list1
               list1 = list1.next
           else:
               current.next = list2
               list2 = list2.next
           current = current.next
       
       return dummy.next
   

11. 面试要点总结

11.1 核心考点

1. 链表操作熟练度：指针操作、节点连接
2. 边界条件处理：空链表、单节点等特殊情况
3. 算法选择：递归 vs 迭代的权衡
4. 代码质量：简洁性、可读性、健壮性

11.2 面试回答要点

问题："请实现合并两个有序链表的算法"

回答框架：

1. 理解题意："这道题要求将两个已排序的链表合并成一个新的有序链表"
2. 分析思路："可以使用双指针技术，比较两个链表当前节点的值"
3. 选择方法："我推荐使用迭代法配合虚拟头节点，空间复杂度更优"
4. 实现代码：写出完整实现
5. 分析复杂度："时间复杂度O(m+n)，空间复杂度O(1)"
6. 测试验证："需要测试空链表、单节点等边界情况"

11.3 进阶问题准备

1. 如何合并K个有序链表？

   • 分治法：两两合并
   • 优先队列：维护K个指针

2. 如何处理链表中的重复元素？

   • 保留重复元素 vs 去除重复元素
   • 稳定性考虑

3. 如何优化大规模数据的合并？

   • 外部排序思想
   • 内存管理策略

11.4 扩展变种

• 合并两个有序数组（LeetCode 88）
• 合并K个有序链表（LeetCode 23）
• 链表排序（LeetCode 148）
• 删除排序链表中的重复元素（LeetCode 83, 82）

12. 总结

核心要点

1. 算法本质：利用已排序特性，使用双指针技术
2. 最优解法：迭代法 + 虚拟头节点，时间O(m+n)，空间O(1)
3. 关键细节：边界处理、指针移动、剩余节点连接
4. 实际应用：数据合并、流处理、分布式系统

学习建议

1. 掌握基础：先理解递归解法，再优化为迭代
2. 注重细节：重点练习边界条件和指针操作
3. 扩展思考：从两个链表扩展到K个链表
4. 实际应用：思考在实际项目中的应用场景

扩展学习

• 学习更复杂的链表操作（反转、环检测等）
• 掌握分治算法在链表问题中的应用
• 了解外部排序和大数据处理技术
• 研究分布式系统中的数据合并策略

这道题是链表操作的经典问题，掌握好它对理解链表数据结构和指针操作非常重要。通过不断练习和思考，可以提高对链表算法的整体理解水平。