Python solutions (iteratively, recursively, iteratively in-place).


  • 81
    C
    # iteratively
    def mergeTwoLists1(self, l1, l2):
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next
        
    # recursively    
    def mergeTwoLists2(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
            
    # in-place, iteratively        
    def mergeTwoLists(self, l1, l2):
        if None in (l1, l2):
            return l1 or l2
        dummy = cur = ListNode(0)
        dummy.next = l1
        while l1 and l2:
            if l1.val < l2.val:
                l1 = l1.next
            else:
                nxt = cur.next
                cur.next = l2
                tmp = l2.next
                l2.next = nxt
                l2 = tmp
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

  • 0
    P

    Brilliant. One question: in the first solution, why do we need two variables, dummy and cur? Why doesn't one, namely cur, work?


  • 3
    C

    If you just use one (like cur) how can you return, due to the fact that cur is not pointing to the head any more.


  • 0
    P

    yeah. you are right. thanks for pointing this out.


  • 1
    G

    It looks like the first solution does it in place, as well as the third solution, but uses less additional variables and less convoluted logic. Am I wrong?


  • 3
    Q
    # solution 1
    def mergeTwoLists(self, l1, l2):
        if l1 is None or (l2 and l1.val>l2.val):
            l1, l2 = l2, l1
        tail = l1
        while tail and l2:
            if tail.next is None or (tail.next.val > l2.val):
                tail.next, l2 = l2, tail.next
            tail = tail.next
        return l1    
    # solution 2, same as OP's solution 1
    def mergeTwoLists1(self, l1, l2):
        head = tail = ListNode(0)
        while l1 and l2:
            if l1.val<=l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 if l1 else l2 # a better way is tail.next = l1 or l2, as in OP's code
        return head.next
    

    Basic idea is start from a List, growing it node by node.

    In solution 2 we have a dummy head, and a tail indicating last node in this growing List. At each step we append either l1 or l2 to tail, and update tail, l1 or l2 accordingly.

    In solution 1, first we make sure l1 is a better list (meaning l2 is None or has larger/equal value, kudos to StefanPochmann, solution 2), and in the end we return l1, tail indicating last node in this growing list too. The list growing is slightly different (in my view, more elegant and more error-prone?), first make sure node to be appended is tail.next (by 0 or 1 swapping), then update tail, there is no need of upadating l1 or l2 as in solution 2.

    In summary, the tradeoff is, solution 1 has more conditional expr, but remove the need of dummy head; for list growing, solution 2 extends from either l1 or l2 then update accordingly, solution 1 first establish betterness of tail.next, making update simpler at the cost of one more test of Noneness of tail.next.

    I prefer solution 2 and appreciate solution 1 more.


  • 0
    S

    I agree with you. The first solution is also in-place, but the third solution use the natural link of l1 which saves much time than first one.


  • 0
    D

    class Solution(object):
    def mergeTwoLists(self,l1,l2):
    dummy = cur = ListNode(0)
    while l1 and l2:
    if l1.val <l2.val:
    cur.next = l1
    l1 = l1.next
    else:
    cur.next = l2
    l2 = l2.next
    cur = cur.next
    cur.next = l1 or l2
    return dummy.next


  • 0
    P

    Can someone please help me understand why I don't get the complete merged list? I used iterative method. I inserted print statements to make sure I see what I expect. I am even returning the HEAD that I saved at the beginning.

    '''
    class Solution(object):
    def mergeTwoLists(self, l1, l2):

        if l1 == None and l2 == None:
            return None
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        my_first = l3 = None
        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                print("If - putting %s" % l1.val)
                if l3 == None:
                    print("If - no L3")
                    l3 = ListNode(l1.val)
                    my_first = l3
                else:
                    l3.next = ListNode(l1.val)
                l1 = l1.next
            else:
                print("Else - putting %s" % l2.val)
                if l3 == None:
                    print("Else - no L3")
                    l3 = ListNode(l2.val)
                    my_first = l3
                else:
                    l3.next = ListNode(l2.val)
                l2 = l2.next
            
        if l1 == None:
            print("rest - l2")
            l3.next = l2
        else:
            print("rest - l1")
            l3.next = l1
        return my_first
    

    '''


  • 0
    P

    @perennial_noob said in Python solutions (iteratively, recursively, iteratively in-place).:

    Can someone please help me understand why I don't get the complete merged list? I used iterative method. I inserted print statements to make sure I see what I expect. I am even returning the HEAD that I saved at the beginning.

    '''
    class Solution(object):
    def mergeTwoLists(self, l1, l2):

        if l1 == None and l2 == None:
            return None
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        my_first = l3 = None
        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                print("If - putting %s" % l1.val)
                if l3 == None:
                    print("If - no L3")
                    l3 = ListNode(l1.val)
                    my_first = l3
                else:
                    l3.next = ListNode(l1.val)
                l1 = l1.next
            else:
                print("Else - putting %s" % l2.val)
                if l3 == None:
                    print("Else - no L3")
                    l3 = ListNode(l2.val)
                    my_first = l3
                else:
                    l3.next = ListNode(l2.val)
                l2 = l2.next
            
        if l1 == None:
            print("rest - l2")
            l3.next = l2
        else:
            print("rest - l1")
            l3.next = l1
        return my_first
    

    '''

    I realized that I was overwriting L3 pointer. I needed: l3 = l3.next
    Refactored code:
    '''
    class Solution(object):
    def mergeTwoLists(self, l1, l2):

        if l1 == None and l2 == None:
            return None
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        my_first = l3 = None
        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                if l3 == None:
                    l3 = ListNode(l1.val)
                else:
                    l3.next = ListNode(l1.val)
                    l3 = l3.next
                l1 = l1.next
            else:
                if l3 == None:
                    l3 = ListNode(l2.val)
                else:
                    l3.next = ListNode(l2.val)
                    l3 = l3.next
                l2 = l2.next
            if my_first == None:
                my_first = l3
            #print(l3)
            
        if l1 == None:
            l3.next = l2
        else:
            l3.next = l1
            
        return my_first
    

    '''


  • 0
    H

    java version

            if (l1 == null && l2 == null) {
                return null;
            }
    
            if (l1 == null) {
                return l2;
            } else if (l2 == null) {
                return l1;
            } else {
                ListNode ans = new ListNode(Integer.MIN_VALUE), curr = ans;
                ans.next = l1;
                while (l1 != null && l2 != null) {
                    if (l1.val < l2.val) {
                        l1 = l1.next;
                    } else { // l1.val >= l2.val 2 1
                        ListNode tmp = curr.next; // null
                        curr.next = l2; // -1 - 1
                        ListNode tmp2 = l2.next; // 4
                        l2.next = tmp; // null
                        l2 = tmp2; // 4
                    }
                    curr = curr.next;
                }
                if (l1 != null) {
                    curr.next = l1;
                }
                if (l2 != null) {
                    curr.next = l2;
                }
                return ans.next;
            }
    

  • 0
    B

    @psnr dummy points to ListNode(0), and dummy.next is the head of the returned list


  • 0
    D

    @qeatzy For the return head.next, why would it return the whole sorted linked list not the next node?


  • 0
    J

    @psnr You need to keep the head node for return, which is done by the dummy one, since cur will move to the tail of the merged list.


  • 0
    Z

    too long and too complicated


  • 0
    M

    @caikehe said in Python solutions (iteratively, recursively, iteratively in-place).:

        if not l1 or not l2:
            return l1 or l2
    
        if None in (l1, l2):
            return l1 or l2
    

    Would anybody be willing to expand on what's happening in these return lines? I don't fully understand the implication of the "or" here. I take it "return l1 and l2" would return the list node which in this case is = None?


  • 0
    T

    Can someone either explain to me how to use these linked lists or provide a link which might help to explain them? Every time I try to do any problem with them I have issues with the implementation. I think I understand conceptually what they are; a collection of nodes which have a value and a pointer that points to the next element of the linked list. Is there a tutorial somewhere on LeetCode that I missed on how to work with the particular implementation provided?


Log in to reply
 

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