Solution by akshaynagpal


  • 0
    A

    Approach #1 Iterative Method [Accepted]

    Intuition

    Keep comparing the list nodes at each step and increment the node pointer that is smaller.
    For example let the given lists be:
    l1: 1->3->8->9 and l2: 2->5->7.
    Since we are merging the sorted lists in ascending order we need to start with finding the smaller node. The smaller node is 1 out of both the lists. Hence we have the head as 1.

    Now the remaining parts of l1 and l2 to be scanned are:
    l1: 3->8->9 and l2: 2->5->7.

    We will append to 1 the smaller node between the above two, which is 2.
    This makes the list as: 1->2.

    Now the remaining parts of l1 and l2 to be scanned are:
    l1: 3->8->9 and l2: 5->7.

    Keep comparing the above until 1 of the 2 lists end. After 3 more comparisons, the merged list is 1->2->3->5->7, l1 is 8->9 and l2 has ended.

    Since both the given lists were sorted we just need to set next of the last node of the merged list (7) to the first node of remaining part of l1 (8). This gives the final merged list as:
    1->2->3->5->7->8->9

    Algorithm

    1. Find the smaller node by comparing val of l1 and l2. Store that node as head.
    2. Copy head to a temporary variable temp. Keep iterating until both lists have a next ListNode and assign the next node to the node with the smaller value among both lists.
    3. When one of the lists finishes, append the remaining nodes of the other list to temp.

    Python

    class Solution(object):
        def mergeTwoLists(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            # if both lists are empty
            if not l1 and not l2:
                return None
            # if one of the lists is empty
            if not l1 or not l2:
                return l1 if l1 else l2
            # find head
            if l1.val <= l2.val:
                head = l1
                l1 = l1.next
            else:
                head = l2
                l2 = l2.next
            # build remaining list
            temp = head
            while l1 and l2:
                if l1.val <= l2.val:
                    temp.next = l1
                    l1 = l1.next
                else:
                    temp.next = l2
                    l2 = l2.next
                temp = temp.next
            # when one of the 2 lists ends, append the remaining list to temp
            if l1:
                temp.next = l1
            if l2:
                temp.next = l2
    
            return head
    

    Complexity Analysis

    • Time complexity : $$O(m+n) $$, where m and n are the size of l1 and l2 respectively. We are iterating both the lists only once in the while loop.

    • Space complexity : $$O(1)$$. We don't need any extra space as we are merging the lists in place.



Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.