[LC] 21. Merge Two Sorted Lists

Merge 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:

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 and l2 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.