21_合并两个有序链表
描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解法一：迭代
思路
因为两个链表都是有序链表（递增），因此可以很容易地找出两个链表中的最小元素，即比较两个链表表头的元素，时间复杂度是 \(O(1)\) 的。我们可以利用两个指针——指向两个链表的最小节点，每次比较两个指针所指向节点的值，将值比较小的节点加到新的链表中，然后更新指针，如此循环往复直到到达一个链表的尾部。最后，还需要将另一个链表的剩余部分（如果存在的话）添加到新的链表的尾部。
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 dummyHead = new ListNode(0);
ListNode lastNode = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
lastNode.next = l1;
l1 = l1.next;
} else {
lastNode.next = l2;
l2 = l2.next;
}
lastNode = lastNode.next;
}
lastNode.next = l1 != null ? l1 : l2;
return dummyHead.next;
}
}
// Runtime: 9 ms
// Your runtime beats 86.44 % of java submissions.
复杂度分析：
- 时间复杂度：\(O(m+n)\)，其中，\(m\) 为链表 1 的节点数，\(n\) 为链表 2 的节点数，算法需要遍历两个链表的所有元素
- 空间复杂度：\(O(1)\)，只需要保存两个引用
Python 实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy_head = last_node = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
last_node.next = l1
l1 = l1.next
else:
last_node.next = l2
l2 = l2.next
last_node = last_node.next
last_node.next = l1 or l2
return dummy_head.next
# Runtime: 44 ms
# Your runtime beats 99.24 % of python3 submissions.
复杂度分析同上。
解法二：递归
思路
递归的思路和迭代的思路是相同的，都是每次比较两个链表的最小节点，然后对值更小的节点进行操作。不同的是，迭代是从值比较小的节点开始组建新的链表，而递归则是从值比较大的节点开始组建新的链表——递归到其中一个链表的尾部才开始组建新的链表。
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 || l2 == null) {
return l1 != null ? l1 : l2;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
// Runtime: 8 ms
// Your runtime beats 99.96 % of java submissions.
复杂度分析：
- 时间复杂度：\(O(m+n)\)，其中，\(m\) 为链表 1 的节点数，\(n\) 为链表 2 的节点数，算法需要遍历两个链表的所有元素
- 空间复杂度：\(O(m+n)\)，额外的空间是由于递归调用占用系统栈的空间，递归的深度最多为 \(m+n\) 层
Python 实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
复杂度分析同上。