对单链表进行排序，要求不使用额外的新链表（即空间复杂度为O(1)），请说明算法思路、时间复杂度，并写出核心代码实现。

回答思路

1. 能明确选择归并排序并阐述分治思路
2. 说明如何通过快慢指针找中点并递归切分
3. 指出原地归并排序的难点及O(1)空间的实现方法
4. 分析时间复杂度为O(n log n)
5. 能正确写出合并两个有序链表的逻辑