LeetCode 剑指 Offer 25. 合并两个排序的链表

Categories:

题目描述
思路分析
1. 解法一：迭代合并（推荐）
相似题目

题目描述

✅ 剑指 Offer 25. 合并两个排序的链表

思路分析

解法一：迭代合并（推荐）

核心思路：

使用虚拟头节点依次比较两条链表节点。

较小节点接到结果链表后，移动对应指针。

最后拼接剩余部分。

复杂度分析：

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

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

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        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
}

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	链表
23. 合并 K 个升序链表	困难	堆
148. 排序链表	中等	归并排序
141. 环形链表	简单	快慢指针
83. 删除排序链表中的重复元素	简单	链表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/12746570