# Python Bottom up Mergesort O(1) space

• ``````    def sortList(self, head):

size = 0
itr = head
while itr:
size, itr = size + 1, itr.next
lng = 1
buffr = ListNode(None)
buffr.next = head
while lng < size:
p = buffr # initialize
l = r = buffr.next
while l:
val = lng
while r and val > 0:
r, val = r.next, val - 1
if not r: break
lc = rc = lng
#similar to merging 2 sorted lists. difference is that,
#we're actually dealing with 2 different sections of a long list
while l and r and lc and rc:
if l.val < r.val:
p.next, p, l, lc = l, l, l.next, lc - 1
else:
p.next, p, r, rc = r, r, r.next, rc - 1
if lc or not r: # trailing elements in left segment
while lc > 1: # move left ptr until last of its segment
p.next = p = l
l, lc = l.next, lc - 1
p.next = p = l # update p to last of lc
l.next = r
else: # trailing elements in right segment
while r and rc:
p.next = p = r
r, rc = r.next, rc - 1
l = r
lng *= 2
return buffr.next
``````

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