LeetCode | Merge Two Sorted Lists | Microsoft Interview Questions | Geek Hacker

Problem Statement

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

Constraints

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

Examples

Example 1

Source: LeetCode

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2

Input: l1 = [], l2 = []
Output: []

Example 3

Input: l1 = [], l2 = [0]
Output: [0]

Analysis

In order to merge 2 sorted linked lists to result in a 1 sorted linked list, we can use merge function of the Merge Sort algorithm.

Merge Sort is a Divide and Conquer algorithm that divides the input list into two halves, calls itself for the two halves, and then merges the two sorted halves.

Algorithm

1. Check if any of the lists is empty.
2. Determine the head of the resultant list. This head will be the smallest head of the given lists.
3. Loop through each node of the lists until one of the lists get traversed completely.
4. While traversing the lists, identify the smaller node in the lists and add it to the resultant list.
5. Once the loop is complete, there may be a case where a list has remaining nodes. We will add these remaining nodes to the resultant list.

Python 3 Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # Check if either of the lists is null
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        
        # Choose head which is smaller of the two lists
        if l1.val < l2.val:
            temp = head = ListNode(l1.val)
            l1 = l1.next
        else:
            temp = head = ListNode(l2.val)
            l2 = l2.next
        # Loop until any of the list becomes null
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                temp.next = ListNode(l1.val)
                l1 = l1.next
            else:
                temp.next = ListNode(l2.val)
                l2 = l2.next
            temp = temp.next
        # Add all the nodes in l1, if remaining
        while l1 is not None:
            temp.next = ListNode(l1.val)
            l1 = l1.next
            temp = temp.next
        # Add all the nodes in l2, if remaining
        while l2 is not None:
            temp.next = ListNode(l2.val)
            l2 = l2.next
            temp = temp.next
        return head

Complexity

Time Complexity

O(m + n) such that m and n are the number of nodes the 2 lists.

Space Complexity

O(1) because we are creating a list to store the result, but we are not using it in the intermediate computations.

For more LeetCode problems’ solutions, visit my GitHub repo.

If you enjoyed reading this article, please recommend and share it to help others find it!