前言：
现在姐妹们对“链表排序的最好时间复杂度”大致比较讲究，兄弟们都想要分析一些“链表排序的最好时间复杂度”的相关资讯。那么小编在网摘上搜集了一些有关“链表排序的最好时间复杂度””的相关内容，希望你们能喜欢，我们快快来学习一下吧！题目
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：输入：head = [] 输出：[]
提示：链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
注意：本题与主站 148 题相同
解题思路分析
1、快排；时间复杂度O(nlog(n))，空间复杂度O(log(n))
func sortList(head *ListNode) *ListNode { quickSort(head, nil) return head}func quickSort(head, end *ListNode) { if head == end || head.Next == end { return } temp := head.Val fast, slow := head.Next, head for fast != end { if fast.Val < temp { slow = slow.Next slow.Val, fast.Val = fast.Val, slow.Val } fast = fast.Next } slow.Val, head.Val = head.Val, slow.Val quickSort(head, slow) quickSort(slow.Next, end)}2、归并；时间复杂度O(nlog(n))，空间复杂度O(log(n))
func sortList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } slow, fast := head, head.Next for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } right := sortList(slow.Next) slow.Next = nil left := sortList(head) return mergeTwoLists(left, right)}func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { res := &ListNode{} temp := res for l1 != nil && l2 != nil { if l1.Val < l2.Val { temp.Next = l1 l1 = l1.Next } else { temp.Next = l2 l2 = l2.Next } temp = temp.Next } if l1 != nil { temp.Next = l1 } else { temp.Next = l2 } return res.Next}3、归并；时间复杂度O(nlog(n))，空间复杂度O(1)
func sortList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } res := &ListNode{Next: head} cur := head var left, right *ListNode length := 0 for cur != nil { length++ cur = cur.Next } for i := 1; i < length; i = i * 2 { cur = res.Next tail := res for cur != nil { left = cur right = split(left, i) cur = split(right, i) tail.Next = mergeTwoLists(left, right) for tail.Next != nil { tail = tail.Next } } } return res.Next}func split(head *ListNode, length int) *ListNode { cur := head var right *ListNode length-- for length > 0 && cur != nil { length-- cur = cur.Next } if cur == nil { return nil } right = cur.Next cur.Next = nil return right}func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { res := &ListNode{} temp := res for l1 != nil && l2 != nil { if l1.Val < l2.Val { temp.Next = l1 l1 = l1.Next } else { temp.Next = l2 l2 = l2.Next } temp = temp.Next } if l1 != nil { temp.Next = l1 } else { temp.Next = l2 } return res.Next}总结Medium题目，题目同leetcode 148.排序链表
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #链表排序的最好时间复杂度
