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
def getHeads(self, head, k):
h1, t1, h2, t2, nextHead = head, None, None, None, None
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:
nextHead = t.next
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):
fakeHead = ListNode(0)
t = fakeHead
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
return fakeHead.next, newTail
def sortList(self, head):
fakeHead = ListNode(0)
fakeHead.next = head
tmp = fakeHead
k = 1
h1, t1, h2, t2, nextHead = self.getHeads(head, k)
while h2:
tmp = fakeHead
while h2:
if t1: t1.next = None
if t2: t2.next = None
mergeHead, mergeTail = self.merge(h1, t1, h2, t2)
tmp.next = mergeHead
tmp = mergeTail
h1, t1, h2, t2, nextHead = self.getHeads(nextHead, k)
tmp.next = h1
k *= 2
h1, t1, h2, t2, nextHead = self.getHeads(fakeHead.next, k)
return fakeHead.next
```