LeetCode Hot 100 链表进阶：K 组翻转与归并排序

一、链表反转进阶

1.1 基础反转 (LeetCode 206)

反转链表是链表操作中最基础的题型。核心在于维护三个指针：前驱 pre、当前 cur 和后继 nxt。每次迭代将当前节点的 next 指向前驱，然后整体后移。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

1.2 部分反转 (LeetCode 92)

当需要反转指定区间 [left, right] 时，关键在于找到反转区间的'前一个节点'和'后一个节点'。使用哑节点（dummy node）可以方便地处理头节点变化的情况。

具体步骤如下：

1. 遍历到 left - 1 位置，记录为 p0。
2. 从 p0.next 开始执行标准的反转逻辑，循环次数为 right - left + 1。
3. 注意连接断点，确保 p0.next 指向新的头，原头节点的 next 指向剩余部分。

class Solution:
    def reverseBetween(self, head, left, right):
        p0 = dummy = ListNode(next=head)
        # 移动到 left 的前一个位置
        for _ in range(left - 1):
            p0 = p0.next
        
        pre = None
        cur = p0.next
        # 执行反转
        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        # 连接断开的部分
        p0.next.next = cur
        p0.next = pre
        return dummy.next

1.3 K 个一组翻转 (LeetCode 25)

这是上述两个问题的组合。我们需要先判断剩余节点是否足够 k 个，如果不够则保持原样。

实现时，可以先统计链表总长度，或者每 k 步检查一次。这里采用先计算长度的方式，逻辑更直观。

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
            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 寻找中间节点 (LeetCode 876)

归并排序的关键是分治，而分治的第一步是找中点。快慢指针是标准解法：快指针走两步，慢指针走一步，当快指针到达末尾时，慢指针恰好在中间。

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

2.2 合并两个有序链表 (LeetCode 21)

合并过程相对简单，使用哨兵节点简化边界处理。比较两个链表当前节点的值，将较小的接入结果链表。

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 排序链表 (LeetCode 148)

综合以上能力，我们可以实现完整的链表排序。递归终止条件是空表或单节点。之后分割链表，分别排序，最后合并。

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
        
        # 递归排序
        l1 = self.sortList(head)
        l2 = self.sortList(slow)
        
        # 合并
        return self.mergeTwoLists(l1, l2)