问题描述

给定链表的头结点head，请你对链表进行升序排序并返回排序后的链表。

格式

输入

• 一个单链表的头结点。

输出

• 排序后的单链表。

样例

样例1

输入

4
4  2  1  3

输出

1  2  3  4

样例2

输入

5
-1  5  3  4  0

输出

-1  0  3  4  5

提示

• 链表中节点的个数范围是 [0, 5 × 10⁴]
• -10⁵ <= Node.val <= 10⁵

进阶

• 你可以在 O(n log n) 的时间复杂度和常数级额外空间下，对链表进行排序吗？