# Python code with O(nlogn) time and O(1) space with natural merge sort

• 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):

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 None

while p:
if p.val < last.val:
break
else:
last = p
p = p.next
return last

# calculate the length
n = 0
while p:
p = p.next
n += 1

if n <= 1:

while True:
if not t1.next:
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
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