LeetCode--148--排序链表(python)

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

示例 1:

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

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

插入排序，肯定超时了，时间复杂度最坏是O(n^2)

 class Solution:

     def sortList(self, head: ListNode) -> ListNode:

         if head==None or head.next==None:

             return head

         dummyY=ListNode(0)

         dummyY.next=head

         p = head

         r = p.next

         p.next=None

         p=r

         while p != None:

             pre = dummyY

             r = p.next

             while pre.next!=None and pre.next.val <p.val:

                 pre = pre.next

             p.next = pre.next

             pre.next = p

             p = r

         return dummyY.next

归并

 class Solution:

     def sortList(self, head: ListNode) -> ListNode:

         if not head or not head.next:return head

         slow,fast = head,head.next

         while fast and fast.next:

             fast,slow=fast.next.next,slow.next

         mid,slow.next=slow.next,None

         left,right=self.sortList(head),self.sortList(mid)

         h=res = ListNode(0)

         while left and right:

             if left.val < right.val :h.next,left=left,left.next

             else:h.next,right=right,right.next

             h=h.next

         h.next=left if left else right

         return res.next

巴特西

LeetCode--148--排序链表(python)

最新文章

热门文章