归并排序

LeetCode 148 https://leetcode.cn/problems/sort-list/description/ 难度：中等 本题使用归并排序。 找到链表的中间结点 head 2 的前一个节点，并断开 head2 与其前一个节点的连接。这样我们就把原链表均分成了两段更短的链表。 分治，递归调用 sortList，分别排序 head（只有前一半）和 head2。 排序后，我们得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点。 时间复杂度：O(nlogn)，其中 n 是链表长度。递归式 T(n)=2T(n/2)+O(n)，由主定理可得时间复杂度为 O(nlogn)。 空间复杂度：O(logn)。递归需要 O(logn) 的栈开销。 ...