# 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
# inplace, 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
Python solutions (iteratively, recursively, iteratively inplace).


# 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 errorprone?), 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.

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
'''

@perennial_noob said in Python solutions (iteratively, recursively, iteratively inplace).:
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
'''

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; }


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

@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.

@caikehe said in Python solutions (iteratively, recursively, iteratively inplace).:
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?

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?