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

• ``````# 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``````

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

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

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

• 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?

• ``````# 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.

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

• 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

• 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
``````

'''

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

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

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

• too long and too complicated

• ``````    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?

• @mze5111

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

Basically the codes above are equivalent. It means if l1 or l2 is an empty list, then return the one which is not.

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