题目描述
给你链表的头结点 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
代码及注释
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
// 边界情况:链表为空或只有一个节点时,直接返回
if head == nil || head.Next == nil {
return head
}
// 使用快慢指针找到链表的中点
slow, fast := head, head
var cur *ListNode
for fast != nil && fast.Next != nil {
cur = slow
slow = slow.Next
fast = fast.Next.Next
}
// 断开链表,将链表分为两部分
cur.Next = nil
// 递归地对左右两部分进行排序
l := sortList(head)
r := sortList(slow)
// 合并两个有序链表
return merge(l, r)
}
func merge(l1 *ListNode, l2 *ListNode) *ListNode {
// 使用哑节点简化代码
var dummy = &ListNode{}
cur := dummy
// 循环比较两个链表的节点,并将较小的节点连接到新链表中
for l1 != nil && l2 != nil {
if l1.Val > l2.Val {
cur.Next = l2
l2 = l2.Next
} else {
cur.Next = l1
l1 = l1.Next
}
cur = cur.Next
}
// 将剩余的节点连接到新链表的末尾
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
// 返回合并后的链表
return dummy.Next
}
代码解释
sortList
函数
-
终止条件:
if head == nil || head.Next == nil { return head }
当链表为空或只有一个节点时,无需排序,直接返回。
-
找到中点:
slow, fast := head, head var cur *ListNode for fast != nil && fast.Next != nil { cur = slow slow = slow.Next fast = fast.Next.Next } cur.Next = nil
使用快慢指针找到链表的中点,并将链表断开,得到两个子链表
l
和r
。 -
递归排序:
l := sortList(head) r := sortList(slow)
使用递归对左右两个子链表进行排序。
-
合并两个排序后的子链表:
return merge(l, r)
调用
merge
函数合并两个排序后的子链表。
merge
函数
-
初始化:
var dummy = &ListNode{} cur := dummy
使用哑节点
dummy
和cur
指针来合并两个链表。 -
比较合并:
for l1 != nil && l2 != nil { if l1.Val > l2.Val { cur.Next = l2 l2 = l2.Next } else { cur.Next = l1 l1 = l1.Next } cur = cur.Next }
比较
l1
和l2
的当前节点值,将较小的节点连接到cur.Next
。 -
处理剩余节点:
if l1 != nil { cur.Next = l1 } else { cur.Next = l2 }
将剩余的
l1
或l2
链接到cur.Next
。