【Day 20】148.排序链表

148.排序链表

题目：

给你链表的头结点 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 * 10^4] 内
-10^5 <= Node.val <= 10^5

---

思路：

1. 递归终止条件

   • 如果链表为空或者只有一个节点，直接返回，因为空链表或单节点链表天然有序。

2. 找到链表中点并切割

   • 使用快慢指针：

     • slow 每次走 1 步，fast 每次走 2 步。
     • 当 fast 到达尾部时，slow 停在 左半段的尾节点。

   • 将链表从中点切开：

     • 这样左半段从 head 开始，右半段从 second 开始，链表被分为两段。

3. 递归排序左右两段

   • 递归地对左右半段进行排序，直到每段只剩 1 个节点或者为空。

   • 递归调用逻辑：

   • 对左半段 head -> ... -> slow 再次执行 sortList：

     • 如果左半段长度 > 1，就会再次找中点、切割、递归。
     • 最终递归到每段只有一个节点，就返回节点。

   • 对右半段 second -> ... 同理。

• 结果：

  • 左右两段分别返回排好序的链表头。

4. 合并两个有序链表

   • 新建一个 dummy 节点作为合并链表的头部辅助节点。
   • 遍历左右两个链表，逐个比较节点值，把小的节点接到当前链表尾部。
   • 当一个链表耗尽，把另一个链表剩下的节点直接接上。

5. 返回合并后的链表

   • dummy.Next 指向合并后的有序链表头。

---

• 时间复杂度：O(n log n)

  • 每次分半是 log n 层，合并两段是 O(n)，总共 O(n log n)。

• 空间复杂度：O(log n)

  • 递归栈的空间，因为链表不需要额外数组。

• 适合链表的原因

  • 链表不适合快速排序那样的随机访问，但归并排序只需要顺序访问，非常自然。

---

代码实现（Go）：

详细注解：

// package main// import "fmt"// type ListNode struct {
// 	Val  int
// 	Next *ListNode
// }func sortList(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head // 空链表或单节点直接返回}// 1. 使用快慢指针找到链表中点slow, fast := head, head.Nextfor fast != nil && fast.Next != nil {slow = slow.Nextfast = fast.Next.Next}second := slow.Next // 右半段头保存起来使用，接下来要置空slow.Next = nil     // 切断链表，分成左右两段，左半段最后指向 nil// 2. 递归排序左右两段left := sortList(head)    // 第一段开头right := sortList(second) // 第二段开头// 3. 合并两个有序链表dummy := &ListNode{}cur := dummyfor left != nil && right != nil {if left.Val < right.Val {cur.Next = leftleft = left.Next} else {cur.Next = rightright = right.Next}cur = cur.Next}if left != nil {cur.Next = left} else {cur.Next = right}return dummy.Next
}// func main() {
// 	// 构造链表 [4,2,1,3]
// 	head := &ListNode{
// 		Val: 4,
// 		Next: &ListNode{
// 			Val: 2,
// 			Next: &ListNode{
// 				Val: 1,
// 				Next: &ListNode{
// 					Val:  3,
// 					Next: nil,
// 				},
// 			},
// 		},
// 	}// 	sorted := sortList(head)
// 	// 打印排序后的链表
// 	for sorted != nil {
// 		fmt.Print(sorted.Val, " ")
// 		sorted = sorted.Next
// 	}
// 	// 输出: 1 2 3 4
// }

无注释：

package mainimport "fmt"type ListNode struct {Val  intNext *ListNode
}func sortList(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head}slow, fast := head, head.Nextfor fast != nil && fast.Next != nil {slow = slow.Nextfast = fast.Next.Next}second := slow.Nextslow.Next = nilleft := sortList(head)right := sortList(second)dummy := &ListNode{}cur := dummyfor left != nil && right != nil {if left.Val < right.Val {cur.Next = leftleft = left.Next} else {cur.Next = rightright = right.Next}cur = cur.Next}if left != nil {cur.Next = left} else {cur.Next = right}return dummy.Next
}func main() {head := &ListNode{Val: 4,Next: &ListNode{Val: 2,Next: &ListNode{Val: 1,Next: &ListNode{Val:  3,Next: nil,},},},}sorted := sortList(head)for sorted != nil {fmt.Print(sorted.Val, " ")sorted = sorted.Next}
}

---