归并排序 链表

### 归并排序实现链表排序 归并排序是一种基于分治法的有效且稳定的排序算法，在处理链表时尤为适用。通过将链表分割为较小的部分，分别对其进行排序后再合并，最终形成一个完整的有序链表。 #### 链表归并排序的核心思想 链表的归并排序通常分为两种方法：自顶向下的递归方式和自底向上的迭代方式。以下是具体实现思路： 1. **分割链表** 将链表分成两部分，直到每部分只有一个节点或者为空为止。这一步可以通过快慢指针来找到链表中间位置[^2]。 2. **递归调用** 对每一半链表继续执行上述过程，直至无法再分割。 3. **合并两个有序链表** 合并两个已经排好序的小链表成为一个新的有序链表。这是整个归并排序的关键步骤之一[^1]。 #### Java 实现代码示例 下面是一个典型的 Java 代码实现，展示了如何利用归并排序对单链表进行排序： ```java class ListNode { int val; ListNode next; ListNode(int x) { this.val = x; this.next = null; } } public class MergeSortLinkedList { public static ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; // 如果链表为空或仅有一个节点，则无需排序 } // 使用快慢指针找到链表中点 ListNode mid = getMid(head); ListNode rightHead = mid.next; mid.next = null; // 断开左半边和右半边的连接 // 递归地对左右两部分进行排序 ListNode leftSorted = sortList(head); ListNode rightSorted = sortList(rightHead); // 合并两个已排序的链表 return merge(leftSorted, rightSorted); } private static ListNode getMid(ListNode head) { ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; // 返回中间节点 } private static ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); // 创建虚拟头结点 ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } // 连接剩余部分 if (l1 != null) { tail.next = l1; } else { tail.next = l2; } return dummy.next; // 虚拟头结点的下一个就是真正的头结点 } } ``` 以上代码实现了链表的归并排序功能，其中 `getMid` 函数用于寻找链表的中间节点，而 `merge` 函数则负责将两个有序链表合并成一个新的有序链表[^3]。 #### 时间与空间复杂度分析 - **时间复杂度**: O(n log n)，因为每次都将链表划分为更小的部分，并逐步将其重新组合起来。 - **空间复杂度**: 自顶向下递归的方式会占用额外栈空间，因此其空间复杂度为 O(log n)[^5]。 对于某些场景（如内存受限），还可以考虑使用自底向上非递归的方法进一步优化空间性能[^4]。 --- ###