面试算法题：排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

思路：这个问题是关于对链表进行排序。对于链表排序，一个高效的方法是使用归并排序（Merge Sort）。归并排序对于链表特别有效，因为它不需要随机访问元素，可以在 O(n log n) 时间复杂度内完成排序，同时只需要 O(1) 的额外空间。

代码：

// ListNode 定义链表节点结构

type ListNode struct {

Val int

Next *ListNode

}

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

}

// 分割链表

mid := slow.Next

slow.Next = nil

// 递归排序两半

left := sortList(head)

right := sortList(mid)

// 合并排序后的两半

return mergeTwoLists(left, right)

}

// 合并两个有序链表

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {

dummy := &ListNode{} // 哑节点

current := dummy

for l1 != nil && l2 != nil {

if l1.Val < l2.Val {

current.Next = l1

l1 = l1.Next

} else {

current.Next = l2

l2 = l2.Next

}

current = current.Next

}

// 处理剩余节点

if l1 != nil {

current.Next = l1

}

if l2 != nil {

current.Next = l2

}

return dummy.Next

}

代码过程：

sortList 函数是主要的排序函数：

首先，我们检查链表是否为空或只有一个节点。如果是，直接返回。

使用快慢指针法找到链表的中点。快指针每次移动两步，慢指针每次移动一步，当快指针到达末尾时，慢指针正好在中点。

在中点处分割链表为两半。

递归地对两半分别进行排序。

最后，合并两个排序后的链表。

mergeTwoLists 函数用于合并两个已排序的链表：

使用一个哑节点（dummy node）来简化操作。

比较两个链表的节点值，将较小的节点连接到结果链表上。

处理剩余的节点。

返回合并后的链表（去掉哑节点）。

这个算法的时间复杂度是 O(n log n)，其中 n 是链表的长度。这是因为我们将链表分成两半的操作是 log n 次，每次合并操作是 O(n)。空间复杂度是 O(log n)，这是由于递归调用栈的深度。