0021 Merge Two Sorted Lists

0021 Merge Two Sorted Lists#

Problem#

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Examples#

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]

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.

Analysis#

Solution#

class Node():
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(A):
    dummy = Node()

    if not A:
        return dummy.next
    
    prev = dummy
    for a in A:
        cur = Node(a)
        prev.next = cur 
        prev = cur
    
    return dummy.next 

def linkedListToList(head):
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res

def mergeTwoLists(list1, list2):
    dummy = Node(0)

    p, p1, p2 = dummy, list1, list2
    
    while p1 and p2:
        if p1.val <= p2.val:
            p.next = p1
            p1 = p1.next
        else:
            p.next = p2    
            p2 = p2.next
        p = p.next
    
    if not p1:
        p.next = p2 
    if not p2:
        p.next = p1 
    
    return dummy.next

# test
list1 = build([1, 2, 4])
list2 = build([1, 3, 4])
merged = mergeTwoLists(list1, list2)
print(linkedListToList(merged))

list1 = build([])
list2 = build([])
merged = mergeTwoLists(list1, list2)
print(linkedListToList(merged))

list1 = build([])
list2 = build([0])
merged = mergeTwoLists(list1, list2)
print(linkedListToList(merged))

[1, 1, 2, 3, 4, 4]
[]
[0]
Contents