The algorithm is described on Wikipedia.
Basically it is similar to a merge sort in bottom-up manner. In each stage, I try to find two adjacent non-decreasing "runs" and merge them. We are done if we have only run left.
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param two ListNodes # @return a ListNode def mergeTwoLists(self, l1, l2): head = ListNode(0) tail = head while True: if not l1: tail.next = l2 break if not l2: tail.next = l1 break if l1.val > l2.val: l1,l2 = l2,l1 tail.next = l1 tail = l1 l1 = l1.next tail.next = None while tail.next: tail = tail.next return head.next, tail def findRun(self, head): if not head: return None if not head.next: return head last = head p = head.next while p: if p.val < last.val: break else: last = p p = p.next return last def natural_mergesort(self, head): # calculate the length n = 0 p = head while p: p = p.next n += 1 # already done if n <= 1: return head while True: t1 = self.findRun(head) h1 = head if not t1.next: # already sorted return h1 tail = None while t1.next: # we have more than one sublist h2 = t1.next t2 = self.findRun(h2) h3 = t2.next t1.next = None t2.next = None newh, newt = self.mergeTwoLists(h1, h2) if not tail: # this is the first pair of runs in this stage head, tail = newh, newt else: tail.next = newh tail = newt if not h3: # no runs any more h1 = t1 = None break else: h1 = h3 t1 = self.findRun(h3) if t1: # we still have one last run tail.next = h1 tail = t1 # @param head, a ListNode # @return a ListNode def sortList(self, head): return self.natural_mergesort(head)