LeetCode 21. 合并两个有序链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：迭代（虚拟头节点 + 双指针）（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 21. 合并两个有序链表

题目：

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

示例 1：

输入：list1 = [1,2,4], list2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：list1 = [], list2 = []
输出：[]

示例 3：

输入：list1 = [], list2 = [0]
输出：[0]

提示：

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

思路分析

解法一：迭代（虚拟头节点 + 双指针）（推荐）

核心思路：

使用虚拟头节点 dummy 简化边界处理。

双指针逐步比较 l1 和 l2 的当前节点，将较小者接到结果链表。

当一侧为空时直接接上另一侧剩余部分。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别表示两条链表的长度。

空间复杂度：O(1)，仅使用常数额外指针。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;

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

        // 将剩余部分整体接上
        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy

	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}

	// 将剩余部分整体接上
	if l1 != nil {
		cur.Next = l1
	} else {
		cur.Next = l2
	}

	return dummy.Next
}

解法二：递归

核心思路：

递归地合并：较小节点作为头结点，其 next 指向递归合并的结果。

终止条件是一条链表为空。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别表示两条链表的长度。

空间复杂度：O(m + n)，递归栈深度与总节点数相同。

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;
        }
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val < list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	}
	list2.Next = mergeTwoLists(list1, list2.Next)
	return list2
}

相似题目

题目	难度	考察点
23. 合并 K 个升序链表	困难	链表、优先队列
88. 合并两个有序数组	简单	双指针
148. 排序链表	中等	链表、归并排序
1634. 求两个多项式链表的和	中等	链表、双指针
1940. 排序数组之间的最长公共子序列	中等	双指针、动态规划
2570. 合并两个二维数组 - 求和法	简单	双指针
86. 分隔链表	中等	链表、双指针
160. 相交链表	简单	链表、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/92434499