2️⃣21. Merge Two Sorted Lists

Easy | Grind 75 | August 15th Monday, 2022

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.

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.

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]

SOLUTIONWe are asked to merge two sorted linked lists into one linked list. Suppose we name list 1 as A and list 2 as B, then we first need to compare the first value of A and B. For instance, if list A has a lower value, we take that value and create a new node(essentially a linked list) with that value. Once we do that, we need to move to the next node in our new linked list as well as on list A. We will repeat this until we have looked at every single node in both lists.

Code: In terms of code implementation, we will first define a new node with the value zero. Let us call this head. We will also have another variable called root that will always point to the head of this new linked list. This is the setup. We will now traverse through both lists. We take the minimum value from the two lists and create a new node with that as our value. Our head.nextpoint to this new node. We then go to the next node of the list we used and also set head as head.next. Given that we traverse only when both lists have nodes(while loop condition), it will always be the case that one list will run out before the other. To handle this, after the while loop is completed, we check if the list still has unvisited nodes. Given both lists are sorted, we can just point ourhead.next to the list that still has nodes (no need to create new nodes).

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # create a head node first
        head = ListNode()
        # store the head of the new node created
        root = head
        
        # traverse until you run out of nodes in one of list
        while l1 and l2: 
            if l1.val <= l2.val: 
                # append to our newly created ndoe
                head.next = ListNode(l1.val)
                l1 = l1.next
                
            else: 
                head.next = ListNode(l2.val)
                l2 = l2.next
                
            # update head as the newly created node
            head = head.next
        
        # given the way we structured our while loop, will always have one list with unvisited nodes. 
        if l1: 
            head.next = l1
        if l2: 
            head.next = l2
            
            
        return root.next

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the total number of nodes. We need to visit each nodes once .

SPACE: O(n), in the worst case, we still need to make n new nodes.