Problem

Link: https://leetcode.com/problems/merge-two-sorted-lists/

In this problem, two input LinkedLists are given which are sorted already. We have to merge these two lists so that the output LinkedList is also sorted.

Solution

To solve this problem

1. First of all, we will create a newList LinkedList. It is the list we have to return at the end. So we will take another node(curr_node) having the same initial value as newList to iterate through the LinkedList.

2. Then with a while loop, we will start checking from the first node of both input LinkedLists. Based on the node that has the smallest value we will take that node and add it to our newList List.

3. If we take a node from list1, we have to update list1 with its next node, the same goes for list2. And after adding a node, don't forget to update the curr_node with its next node.

4. We would follow step 3 until any of the input lists come to an end.

5. As the given lists are sorted already, after the loop ends, we have to add the rest nodes of the remaining lists to our newList list.

Code

# 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]:
        newList = ListNode()
        curr_node = newList

        while list1 and list2:
            if list1.val < list2.val:
                curr_node.next = list1
                list1 = list1.next
            else:
                curr_node.next = list2
                list2 = list2.next
            curr_node = curr_node.next
        if list1 :
            curr_node.next = list1
        elif list2 :
            curr_node.next = list2

        return newList.next

Complexity

m = length of list1

n = length of list2

space complexity : O(m+n) --> as we are using a new list of length m+n

time complexity : O(min(m,n)) --> the while loop ends when the smaller list comes to an end.