【问题】

Sort a linked list in O(n log n) time using constant space complexity.

【代码】

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if head == None or head.next == None:
    		return head
    	fast = head
    	slow = head
    	while fast.next != None and fast.next.next != None:
    		fast = fast.next.next
    		slow = slow.next
    	head1 = head
    	head2 = slow.next
    	slow.next = None
    	head1 = self.sortList(head1)
    	head2 = self.sortList(head2)
    	head = self.merge(head1, head2)
    	return head

    #Merge
    def merge(self, head1, head2):
    	if head1 == None: return head2
    	if head2 == None: return head1
    	head = ListNode(0)
    	pre = head
    	while head1 != None and head2 != None:
    		if head1.val < head2.val:
    			pre.next = head1
    			head1 = head1.next
    		else:
    			pre.next = head2
    			head2 = head2.next
    		pre = pre.next
    	if head1 == None:
    		pre.next = head2
    	if head2 == None:
    		pre.next = head1
    	return head.next