# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
slow = head
fast = head
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
fast = slow.next
slow.next = None
# If we just assume that the p1,p2 are the sorted lists,
# then we can came up with the conclusion that the algo with return sorted list.
p1 = self.sortList(head)
p2 = self.sortList(fast)
return self.merge(p1, p2)
def merge(self, list1, list2):
dummy = ListNode(0)
p = dummy
while list1 and list2:
if list1.val <= list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
if not list1:
p.next = list2
if not list2:
p.next = list1
return dummy.next