25. 合并两个排序的链表

---

comments: true
difficulty: 简单
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9825.%20%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%8E%92%E5%BA%8F%E7%9A%84%E9%93%BE%E8%A1%A8/README.md

面试题 25. 合并两个排序的链表

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode.cn/problems/merge-two-sorted-lists/

解法

方法一：迭代

我们先创建一个虚拟头结点 dummy，然后创建一个指针 cur 指向 dummy。

接下来，循环比较 l1 和 l2 的值，将较小的值接在 cur 后面，然后将指针向后移动一位。循环结束，将 cur 指向 l1 或者 l2 中剩余的部分。

最后返回 dummy.next 即可。

时间复杂度 $O(m+n)$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别为两个链表的长度。

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:dummy = cur = ListNode(0)while l1 and l2:if l1.val <= l2.val:cur.next = l1l1 = l1.nextelse:cur.next = l2l2 = l2.nextcur = cur.nextcur.next = l1 or l2return dummy.next

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
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 ? l2 : l1;return dummy.next;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* dummy = new ListNode(0);ListNode* cur = dummy;while (l1 && l2) {if (l1->val <= l2->val) {cur->next = l1;l1 = l1->next;} else {cur->next = l2;l2 = l2->next;}cur = cur->next;}cur->next = l1 ? l1 : l2;return dummy->next;}
};

Go

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {dummy := &ListNode{}cur := dummyfor l1 != nil && l2 != nil {if l1.Val <= l2.Val {cur.Next = l1l1 = l1.Next} else {cur.Next = l2l2 = l2.Next}cur = cur.Next}if l1 == nil {cur.Next = l2} else {cur.Next = l1}return dummy.Next
}

TypeScript

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*/function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {const dummy = new ListNode(0);let cur = dummy;while (l1 && l2) {if (l1.val <= l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}cur.next = l1 || l2;return dummy.next;
}

Rust

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {pub fn merge_two_lists(mut l1: Option<Box<ListNode>>,mut l2: Option<Box<ListNode>>,) -> Option<Box<ListNode>> {match (l1.is_some(), l2.is_some()) {(false, false) => None,(true, false) => l1,(false, true) => l2,(true, true) => {let mut dummy = Box::new(ListNode::new(0));let mut cur = &mut dummy;while l1.is_some() && l2.is_some() {cur.next = if l1.as_ref().unwrap().val < l2.as_ref().unwrap().val {let mut res = l1.take();l1 = res.as_mut().unwrap().next.take();res} else {let mut res = l2.take();l2 = res.as_mut().unwrap().next.take();res};cur = cur.next.as_mut().unwrap();}cur.next = if l1.is_some() { l1.take() } else { l2.take() };dummy.next.take()}}}
}

JavaScript

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*/
/*** @param {ListNode} l1* @param {ListNode} l2* @return {ListNode}*/
var mergeTwoLists = function (l1, l2) {const dummy = new ListNode(0);let cur = dummy;while (l1 && l2) {if (l1.val <= l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}cur.next = l1 || l2;return dummy.next;
};

C#

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public 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 ? l2 : l1;return dummy.next;}
}

Swift

/* public class ListNode {
*     var val: Int
*     var next: ListNode?
*     init(_ val: Int) {
*         self.val = val
*         self.next = nil
*     }
* }
*/class Solution {func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {let dummy = ListNode(0)var cur: ListNode? = dummyvar l1 = l1var l2 = l2while let l1Node = l1, let l2Node = l2 {if l1Node.val <= l2Node.val {cur?.next = l1Nodel1 = l1Node.next} else {cur?.next = l2Nodel2 = l2Node.next}cur = cur?.next}cur?.next = l1 ?? l2return dummy.next}
}

方法二：递归

我们先判断 l1 和 l2 中有没有一个为空，如果有一个为空，那么我们直接返回另一个链表即可。

接下来，我们比较 l1 和 l2 的值：

• 如果 l1 的值小于等于 l2 的值，我们递归调用 mergeTwoLists(l1.next, l2)，并将 l1.next 指向返回的链表，然后返回 l1。
• 如果 l1 的值大于 l2 的值，我们递归调用 mergeTwoLists(l1, l2.next)，并将 l2.next 指向返回的链表，然后返回 l2。

时间复杂度 $O(m+n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为两个链表的长度。

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:if l1 is None or l2 is None:return l1 or l2#回溯时，将产生有序合并if l1.val <= l2.val:l1.next = self.mergeTwoLists(l1.next, l2)return l1else:l2.next = self.mergeTwoLists(l1, l2.next)return l2

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}if (l1.val <= l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (!l1) {return l2;}if (!l2) {return l1;}if (l1->val <= l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

Go

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {if l1 == nil {return l2}if l2 == nil {return l1}if l1.Val <= l2.Val {l1.Next = mergeTwoLists(l1.Next, l2)return l1} else {l2.Next = mergeTwoLists(l1, l2.Next)return l2}
}

TypeScript

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*/function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {if (l1 == null || l2 == null) {return l1 || l2;}if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;}l2.next = mergeTwoLists(l1, l2.next);return l2;
}

Rust

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {pub fn merge_two_lists(l1: Option<Box<ListNode>>,l2: Option<Box<ListNode>>,) -> Option<Box<ListNode>> {match (l1, l2) {(Some(mut n1), Some(mut n2)) => {if n1.val < n2.val {n1.next = Self::merge_two_lists(n1.next, Some(n2));Some(n1)} else {n2.next = Self::merge_two_lists(Some(n1), n2.next);Some(n2)}}(Some(node), None) => Some(node),(None, Some(node)) => Some(node),(None, None) => None,}}
}

JavaScript

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*/
/*** @param {ListNode} l1* @param {ListNode} l2* @return {ListNode}*/
var mergeTwoLists = function (l1, l2) {if (!(l1 && l2)) {return l1 || l2;}if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l2.next, l1);return l2;}
};

C#

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution {public ListNode MergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}if (l1.val <= l2.val) {l1.next = MergeTwoLists(l1.next, l2);return l1;} else {l2.next = MergeTwoLists(l1, l2.next);return l2;}}
}