题解
时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 On2次，其中最适合链表的排序算法是归并排序。
坑点：链表中节点的数目在范围 [0, 5 * 104] 内，没注意节点可能为0，没写head == nil，排错排了好久
思路：归并排序，找中点和合并操作
代码
package main type ListNode struct { Val int Next *ListNode } //递归到只有一个数字的时候返回，然后再合并 func sortList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } mid := findMiddle(head) tail := mid.Next mid.Next = nil left := sortList(head) right := sortList(tail) return mergeTwoLists(left, right) } //快慢指针找链表的中点 func findMiddle(head *ListNode) *ListNode { slow := head fast := head.Next for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } return slow } //golang力扣leetcode 21.合并两个有序链表 func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} head := dummy for l1 != nil && l2 != nil { if l1.Val < l2.Val { head.Next = l1 l1 = l1.Next } else { head.Next = l2 l2 = l2.Next } head = head.Next } if l1 != nil { head.Next = l1 l1 = l1.Next head = head.Next } else if l2 != nil { head.Next = l2 l2 = l2.Next head = head.Next } return dummy.Next } func main() { sortList(nil) }
