LeetCode Hot 100 链表进阶：反转与排序实战 (Python)

注意这里的连接顺序：p0.next 指向新的头节点（原 right 位置），而原 left 位置节点的 next 应指向 cur（即 right+1 位置）。

分组反转：25. K 个一组翻转链表

这是上述两个问题的综合应用。我们需要判断剩余节点是否足够 k 个，如果是则进行反转，否则保持原样。这涉及到先统计长度，再分段处理。

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
            
        dummy = ListNode(0)
        dummy.next = head
        p0 = dummy
        pre = None
        cur = head
        
        while n >= k:
            # 重置当前段的指针状态
            pre = None
            # 反转 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 到当前段的尾部，准备下一组
            p0 = nxt
            n -= k
            
        return dummy.next

这段代码稍微复杂一些，因为涉及多组连接。p0 始终指向上一组的尾节点，每次反转后，p0.next 指向新组的头，而旧组的头（nxt）指向下一组的开始（cur）。

链表排序：148. 排序链表

链表无法像数组那样随机访问，因此快速排序的空间复杂度较高，归并排序是更优选择。归并排序要求时间复杂度 O(n log n)，空间复杂度 O(1) 或 O(log n)。

辅助函数：找中点与合并

归并排序的第一步是找到中点断开链表。快慢指针是标准解法：fast 走两步，slow 走一步，当 fast 到达末尾时，slow 恰好在中间。

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

合并两个有序链表则是双指针的经典应用，利用哨兵节点避免空指针判断。

def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
    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

完整排序实现

结合上述两个辅助函数，递归地分割和合并即可。

def sortList(self, head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    
    # 找到中点并断开
    mid = self.middleNode(head)
    prev = None
    curr = head
    while curr != mid:
        prev = curr
        curr = curr.next
    prev.next = None
    
    # 分治
    left = self.sortList(head)
    right = self.sortList(mid)
    
    # 合并
    return self.mergeTwoLists(left, right)

在实际编码中，middleNode 返回的是后半段的头，我们需要确保前半段的尾节点被置空。上面的实现通过遍历找到了 mid 的前驱，从而安全断开链表。

总结

链表题的核心在于画图理解指针变化。无论是反转还是排序，都要特别注意断链和重连的顺序。使用哑节点（Dummy Node）能极大减少边界条件的判断，让代码更健壮。掌握这些模式后，面对复杂的链表变形题也能从容应对。