Merge Two Sorted Lists

Constraints

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Idea #1 (Time: N, Memory: N)

1. Compare value of each list head node.
2. Bigger one will be added in res list.
3. If one of head node doesn't exit, add left one to res list.

Idea #2 (Time: N log N, Memory: N)

1. Parse all linked list to list
2. Concatenate lists
3. Sort using quick sort algorithm
4. Convert List to Linked List

Test Cases

Example 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Code

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        node = ListNode(val=0)
        res = node
        tmp = None
        while list1 and list2:
            # Compare value of each list head node
            if list1.val <= list2.val:
                # Bigger one will be added in res list.
                tmp = list1
                list1 = list1.next
            else:
                tmp = list2
                list2 = list2.next
            node.next = ListNode(tmp.val)
            node = node.next
        # If one of head doesn't exit, add left one to res list.
        if list1 and not list2:
            tmp = list1
        elif not list1 and list2:
            tmp = list2
        else: return None
        while tmp:
            node.next = ListNode(tmp.val)
            node = node.next
            tmp = tmp.next
        return res.next