【问题】
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