LeetCode 链表进阶：K 组翻转与归并排序实战（Python）

1.3 K 个一组翻转

在 25 题中，要求每 k 个节点为一组进行翻转。如果剩余节点不足 k 个，则保持原样。这其实是上述'部分区间反转'的多次复用。

实现步骤如下：

1. 先遍历一遍链表统计总长度 n。
2. 只要剩余节点数 n >= k，就截取一段进行反转。
3. 更新指针位置，继续下一轮。

这里要注意，每次反转完，需要将上一组的尾节点指向当前组的头节点，否则链表会断开。

class Solution:
    def reverseKGroup(self, head, k):
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        
        p0 = dummy = ListNode(next=head)
        pre = None
        cur = head
        
        while n >= k:
            n -= k
            # 局部反转 k 个节点
            for _ in range(k):
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            
            # 连接上一段的尾部
            nxt = p0.next
            nxt.next = cur
            p0.next = pre
            p0 = nxt
        
        return dummy.next

二、排序链表

2.1 寻找中间节点

归并排序的核心是分治，而链表分治的第一步是找到中点。快慢指针是解决此类问题的标准解法：fast 每次走两步，slow 每次走一步，当 fast 到达末尾时，slow 正好在中点。

class Solution:
    def middleNode(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

2.2 合并两个有序链表

在归并排序的最后一步，需要合并两个已排序的子链表。使用双指针比较节点值，将较小的节点接入新链表。为了简化代码，引入哨兵节点 dummy。

class Solution:
    def mergeTwoLists(self, list1, list2):
        cur = dummy = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        
        cur.next = list1 if list1 else list2
        return dummy.next

2.3 完整排序实现

结合上述两个辅助函数，我们可以实现链表的归并排序。递归终止条件是链表为空或只有一个节点。找到中点后，断开链表，分别对前后两段递归排序，最后合并结果。

需要注意的是，在调用 middleNode 后，必须手动断开 head 和 head2 的连接，否则会导致死循环或逻辑错误。

class Solution:
    def sortList(self, head):
        if not head or not head.next:
            return head
        
        # 找中点并断开
        slow = fast = head
        pre = None
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None
        
        # 分治
        head1 = self.sortList(head)
        head2 = self.sortList(slow)
        
        # 合并
        return self.mergeTwoLists(head1, head2)

总结

链表操作往往比数组更考验指针控制能力。在处理反转、分割、合并等场景时，善用哨兵节点能减少大量边界判断。对于排序类题目，归并排序是链表的最优解，因为它不需要额外空间且时间复杂度稳定为 O(n log n)。