Python easy to understand solution


  • 4

    Let's say

    l1: 3 -> 5 -> 10 -> 19 -> 25 -> ...
    l2: 1 -> 16 -> 33 -> ...
    

    So we can compare a head of l1 and l2 then 1 is the lower one, so just create a new list and link 1 to it, then proceed the cursor on l2.

    l1: 3 ->5 -> 10 -> 19 -> 25 -> ...
    l2: 16 -> 33 -> ...
    result: 1
    

    Next, compare 3 and 16 and do the same thing as the previous step.

    l1: 5 -> 10 -> 19 -> 25 -> ...
    l2: 16 -> 33 -> ...
    result: 1 -> 3
    

    We can continue this process until either l1 or l2 becomes empty. After that, you may just link the rest to the tail of result.

    class Solution(object):
        def mergeTwoLists(self, l1, l2):
            #dummy is necessary for the initial state
            dummyHead = ListNode(None)
            curNode   = dummyHead
            while True:
                # When one node becomes empty
                if not l1:
                    curNode.next = l2
                    l2 = None
                    break
                if not l2:
                    curNode.next = l1
                    l1 = None
                    break
                
                if l1.val > l2.val:
                    curNode.next = l2
                    l2 = l2.next
                else:
                    curNode.next = l1
                    l1 = l1.next
                curNode = curNode.next
            return dummyHead.next

Log in to reply
 

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