21. Merge Two Sorted Lists (Python)

Related Topic

Linked-List.

Description

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Sample I/O

Example 1

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Methodology

We need to creat a head node that allow us to return the head of the merged list. We need two pointers for each linked list. We will compare the value of each pointer and put the smaller value node into the merged linked list and update the pointer to next. We iterate both linked list at same time until one reach to end. Return the head. (We can also use heap to solve this question or even more complecated question for example merge k sorted linked lists where k is greater than 2)

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = new_list = ListNode(0)
        
        while(l1 and l2):
            if (l1.val < l2.val):
                new_list.next = l1
                l1 = l1.next  
            else:
                new_list.next = l2
                l2 = l2.next
            new_list = new_list.next

        new_list.next = l1 or l2
        return head.next

BigO

Time complexity : O(n + m)

Because exactly one of l1 and l2 is incremented on each loop iteration, the while loop runs for a number of iterations equal to the sum of the lengths of the two lists. All other work is constant, so the overall complexity is linear.