TikTok 链表分组翻转：完整组探测与指针不变量

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练单链无环，k 为正整数，不复制节点；不足 k 的尾组保持原序。

解题路线

1. 整链反转维护 previous/current/following，改当前 next 前先保存 following。局部更新始终保留尚未处理链。
2. 分组使用 dummy 和 before，先前进 k 步确认完整组，确定 last 与 after；不完整时直接返回，避免翻一半才发现不足。
3. 把 previous 初始化为 after，在组内反向链接，使旧组头自然指向后续链；before.next 接 last，before 移到旧组头。
4. 正确性来自已完成前缀顺序正确、before 指向其尾、后缀未改；一次翻组后重新满足不变量。

手动走一遍

1→2→3→4→5，k=2 得2→1→4→3→5；k=3 得3→2→1→4→5；k=1原序。整链反转从1→2→3变3→2→1，尾 next 必须 None。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next


def reverse(head):
    previous = None
    while head:
        following = head.next
        head.next = previous
        previous, head = head, following
    return previous


def reverse_k_group(head, k):
    """Reverse complete groups only; preserve a short final group. Acyclic input."""
    if k < 1:
        raise ValueError('k must be positive')
    dummy = Node(None, head)
    before = dummy
    while True:
        last = before
        for _ in range(k):
            last = last.next
            if last is None:
                return dummy.next
        after = last.next
        current, previous = before.next, after
        while current is not after:
            following = current.next
            current.next = previous
            previous, current = current, following
        old_first = before.next
        before.next = last
        before = old_first

复杂度

O(n) 时间、O(1) 工作空间；每完整组定位和翻转各至多 k 步，无递归深度风险。

易错点与追问

容易失分的边界

• 先改 next 再保存后继。
• 尾组不足时仍翻转。
• 新组尾接错产生环。

继续深挖

• 不足 k 也反转时怎么改？
• 如何证明复用节点且没有丢失？