题目

给定链表的头结点 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.排序链表