归并排序算法解析与链表排序实战

markdown复制## 1. 归并排序算法精要解析

归并排序（Merge Sort）作为分治思想的经典实现，其核心在于"分解-解决-合并"的三段式策略。我在处理链表类问题时发现，相比数组排序，链表版的归并排序具有天然优势——不需要额外空间进行元素移动。算法时间复杂度稳定在O(nlogn)，空间复杂度根据实现方式不同在O(1)到O(n)之间浮动。

> 关键特性：归并排序是少数几个在最坏情况下仍保持O(nlogn)时间复杂度的排序算法之一，这个特性使其特别适合处理大规模数据排序问题。

典型的分治过程表现为：
1. 分割阶段：递归地将当前序列平分成两个子序列，直到子序列长度为1
2. 合并阶段：将两个已排序的子序列合并成一个有序序列，这是算法的核心操作

## 2. 力扣经典题目实战拆解

### 2.1 链表排序问题（LeetCode 148）

这道题要求对链表进行O(nlogn)时间复杂度的排序，且只能使用常数级额外空间。归并排序的链表实现完美契合这些要求：

```python
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # 快慢指针找中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 分割链表
        mid = slow.next
        slow.next = None
        
        # 递归排序
        left = self.sortList(head)
        right = self.sortList(mid)
        
        # 合并两个有序链表
        dummy = ListNode(0)
        curr = dummy
        while left and right:
            if left.val < right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next
            curr = curr.next
        curr.next = left if left else right
        return dummy.next

2.2 合并K个升序链表（LeetCode 23）

这道hard题目可以看作归并排序的进阶应用，采用分治策略将多路合并转化为两两合并：

python复制class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        
        mid = len(lists) // 2