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)

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

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

Parse all linked list to list
Concatenate lists
Sort using quick sort algorithm
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

Blog

Merge Two Sorted Lists

Se-ok Jeon

Constraints

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

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

Test Cases

Example 1

Example 2:

Example 3:

Code

Join Our Newsletter. No Spam, Only the good stuff.

Related