Python recursive/Iterative solutions


  • 1
    T

    Recursive solution

    class Solution(object):
        def mergeTwoLists(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            if l1==None:
            	if l2!=None:
            		return l2
            	else:
            		return None
            else:
            	if l2==None:
            		return l1
            if l1.val<=l2.val:
            	head=l1
            	head.next=self.mergeTwoLists(l1.next,l2)
            else:
            	head=l2
            	head.next=self.mergeTwoLists(l1,l2.next)
            return head
    

    Iteration

    class Solution(object):
        def mergeTwoLists(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            base=ListNode(0)
            l3=base
            while l1 or l2:
            	if l1==None:
            		l3.next=l2
            		l2=l2.next
            	elif l2==None:
            		l3.next=l1
            		l1=l1.next
            	elif l1.val<=l2.val:
            		l3.next=l1
            		l1=l1.next
            	else:
            		l3.next=l2
            		l2=l2.next
            	l3=l3.next
            return base.next
    

  • 0
    Y

    For the iteration one, when l1 ==None or l2 ==None,
    you can simply break the loop after setting l3.next.
    This will save a little bit time in some cases.


Log in to reply
 

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