给定一个链表，其中元素按组排列，每组内部降序，组与组之间升序（例如3-2-1-5-4-6-7-9-8，组大小分别为3、3、3），如何将整个链表排序为全局升序？请说明思路并实现。

Question

给定一个链表，其中元素按组排列，每组内部降序，组与组之间升序（例如3->2->1->5->4->6->7->9->8，组大小分别为3、3、3），如何将整个链表排序为全局升序？请说明思路并实现。

Accepted Answer

考察点：考察链表排序算法选择、分组边界处理与原地操作能力。回答思路：识别每组与组间的有序结构，说明排序策略 正确拆分和合并节点，不丢失或重复节点 实现全局升序，且时间复杂度合理 代码边界处理（空链表、不同组大小）正确

给定一个链表，其中元素按组排列，每组内部降序，组与组之间升序（例如3->2->1->5->4->6->7->9->8，组大小分别为3、3、3），如何将整个链表排序为全局升序？请说明思路并实现。