# Python O(nlogn) time, O(1) space solution with explanation

• Merge Sort: Sort every 2 elements from head to tail, then start again from head, sort every 4 elements, and so on.

So I start with k = 1, which means sort every 2 elements (k elements in my first list, and some elements <= k in my second list), then I sort again with k = k*2, etc, until my first list has k or more elements, then I know we're finished.

In order to sort every 2*k elements, I just merge sort them. The only hard part here is to get the heads of the 2 lists and merge them. That is implemented in the function getHeads(head, k), where head is the head of the first list of the pair of list we want to merge.

The algorithm sounds simple, but it took me a while to make it correct in my code. Here it is:

``````class Solution(object):
# Get head and tail of list1 and list 2 with k elements
# If there is not enough elements, we just cut there and
# leave them NULL
t = h1
count = 1
while t and t.next and count < k:
count += 1
t = t.next
t1 = t
if t1:
h2 = t.next
t = t.next
count += 1
while t and t.next and count < 2*k:
count += 1
t = t.next
t2 = t
if t2:
return h1, t1, h2, t2, nextHead

# Merge 2 sorted LinkedLists and return their merged list's head and tail
def merge(self, h1, t1, h2, t2):
while h1 and h2:
if h1.val <= h2.val:
t.next = h1
h1 = h1.next
else:
t.next = h2
h2 = h2.next
t = t.next
if h1:
t.next = h1
newTail = t1
else:
t.next = h2
newTail = t2

k = 1
while h2:
while h2:
if t1: t1.next = None
if t2: t2.next = None
mergeHead, mergeTail = self.merge(h1, t1, h2, t2)
tmp = mergeTail
tmp.next = h1
k *= 2
``````

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