题目内容

给定一个单链表，链表中每个节点保存一个整数。请重新排列链表中所有节点的顺序，使节点值按照升序依次连接，并返回重排后链表的头节点。

约束条件：

• 链表节点的数量在 $0$ 到 $5 \times 10^4$ 之间（含端点）。
• 每个节点的值满足 $-10^5 \le \textit{val} \le 10^5$。

输入描述

输入包含一个参数：head，表示待排序链表的头节点。该节点属于链表结构，包含一个整数值 val 和一个指向下一节点的指针 next；链表可能为空。

输出描述

返回一个链表头节点，表示已经按升序排列好的链表。

样例1

输入

42

输出

42

说明

链表只有一个节点，值 42。它已经按升序排列，因此排序后的链表仍然是 42。

样例2

输入

-7 -2 -7 0 -3

输出

-7 -7 -3 -2 0

说明

链表中节点值依次为 -7、-2、-7、0、-3。按升序排列后，两个 -7 排在最前面，接着是 -3、-2，最后是 0。所以输出为 -7 -7 -3 -2 0。

样例3

输入

100000 -100000 0 100000

输出

-100000 0 100000 100000