```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode} head
# @return {ListNode}
def sortList(self, head):
size, node = 0, head
while node:
node = node.next
size += 1
return self.merge_sort(head, size)
def merge_sort(self, head, size):
if size <= 1:
return head
right = prev = head
left_size = size/2
right_size = size - left_size
for i in range(left_size):
prev = right
right = right.next
prev.next = None # divide list to two part
left = self.merge_sort(head, left_size)
right = self.merge_sort(right, right_size)
return self.merge(left, right)
def merge(self, l1, l2):
vhead = curr = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return vhead.next
```