排序链表

中英题面

在O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序。

Sort a linked list inO(nlogn) time using constant space complexity.

示例 1:

　　输入: 4->2->1->3
　　输出: 1->2->3->4

Example 1:

　　Input: 4->2->1->3
　　Output: 1->2->3->4

示例 2:

　　输入: -1->5->3->4->0
　　输出: -1->0->3->4->5

Example 2:

　　Input: -1->5->3->4->0
　　Output: -1->0->3->4->5  <br /><br /><br /><br />

算法

直接套用归并排序的思想，为了方便与节省空间，牺牲了一些常数时间。
时间复杂度：
O(NlogN)
空间复杂度：
O(1)

代码

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def sortList(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         if (not head):
             return None
         if (not head.next):
             return head
         hen = tai = tail = head
         while (tai.next):
             tai = tai.next
             if (tai.next):
                 tail = tail.next
             else:
                 break
             tai = tai.next
         self.adjust(head, tai)
         hen = tail.next
         tail.next = None
         self.adjust(head, tail)
         self.adjust(hen, tai)
         self.sortList(head)
         self.sortList(hen)
         i = head
         while (hen):
             if (i.next):
                 if (i.next.val > hen.val):
                     hen.next, i.next, hen = i.next, hen, hen.next
                 i = i.next
             else:
                 i.next = hen
                 break
         return head
 
     def adjust(self, head, tail):
         i = head
         while (i.next):
             if (head.val > i.next.val):
                 head.val, i.next.val = i.next.val, head.val
             if (tail.val < i.next.val):
                 tail.val, i.next.val = i.next.val, tail.val
             i = i.next