[LC] 21. Merge Two Sorted Lists
TechMerge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
![](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg)
Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = [] Output: []
Example 3:
Input: l1 = [], l2 = [0] Output: [0]
Constraints:
- The number of nodes in both lists is in the range
[0, 50]
. -100 <= Node.val <= 100
- Both
l1
andl2
are sorted in non-decreasing order.
Approach
Easy question. Just iterate both lists and connect to the temporary head list. If l1 or l2 is done, keep doing there is no remain node.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
combined = ListNode(0)
head = combined
while l1 and l2:
if l1.val < l2.val:
combined.next = l1
l1, combined = l1.next, combined.next
else:
combined.next = l2
l2, combined = l2.next, combined.next
while l1:
combined.next = l1
l1, combined = l1.next, combined.next
while l2:
combined.next = l2
l2, combined = l2.next, combined.next
return head.next
Time Complexity: O(N+M)
Space Complexity: O(1) (constant)
Submission
Runtime: 40 ms, faster than 49.99% of Python3 online submissions for Merge Two Sorted Lists.
Memory Usage: 14.4 MB, less than 34.26% of Python3 online submissions for Merge Two Sorted Lists.