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

目录

力扣经典150题第五十八题：合并两个有序链表示例提示解题思路

力扣经典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 <= 100l1 和 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

}

}

推荐文章