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