力扣经典150题第五十八题：合并两个有序链表

用户8589624

发布于 2025-11-13 16:14:56

860

文章被收录于专栏：nginxnginx

力扣经典150题第五十八题：合并两个有序链表

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

示例

示例 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 均按非递减顺序排列

解题思路

本题可以通过递归或迭代的方式合并两个有序链表。具体步骤如下：

创建一个新的链表 dummyHead 作为结果链表的头节点，并初始化指针 curr 指向 dummyHead。
比较两个链表 l1 和 l2 当前节点的值，将值较小的节点连接到结果链表的尾部，并将指针 curr 移动到下一个节点。
当其中一个链表遍历完成时，将另一个链表剩余的部分直接连接到结果链表的尾部。
返回结果链表的头节点。

以下是 Java 代码示例：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeTwoSortedLists {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        return dummyHead.next;
    }

    public static void main(String[] args) {
        MergeTwoSortedLists solution = new MergeTwoSortedLists();

        // 创建示例链表
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        // 测试示例
        ListNode result = solution.mergeTwoLists(l1, l2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        // 输出：1 1 2 3 4 4
    }
}

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/047ad3b0258c41ac9be8a4b66753c41a.png)

```java
public class BlogEnding {

    public static void main(String[] args) {
        encourageEngagement();
    }

    public static void encourageEngagement() {
        System.out.println("🚀 感谢您阅读本文！如果您觉得有收获，请一键三连：点赞 ❤️️、转发 🔁、评论 💬，并加关注哦！");
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-21，如有侵权请联系 cloudcommunity@tencent.com 删除

链表