C++实现k个一组反转链表返回原链表问题排查

问题原因排查 #

你的代码返回原链表的核心问题出在kReverse函数的遍历分组循环条件写反：

• 你写的循环条件是 while (temp != NULL && count == k - 1)，初始count=0，当k>=2时，0 == k-1永远不成立，循环一次都不会执行
• 这就导致temp始终指向当前分组的头节点，每次拆分出来的待反转分组只有1个节点，反转单个节点不会有任何变化，最终整体结果和原链表完全一致

额外问题 #

除了上述核心bug外，你的代码还缺少「不足k个的分组不反转」的逻辑：当前逻辑无论分组长度是否够k，都会执行反转，不符合题目要求。

修正后的代码 #

class Pair {
public:
    Node *head;
    Node *tail;
};

Pair reverse(Node *head) {
    if (head == NULL || head->next == NULL) {
        Pair ans;
        ans.head = head;
        ans.tail = head;
        return ans;
    }
    Pair smallAns = reverse(head->next);
    smallAns.tail->next = head;
    head->next = NULL;
    Pair ans;
    ans.head = smallAns.head;
    ans.tail = head;
    return ans;
}

Node *kReverse(Node *head, int k) {
    if (head == NULL) {
        return head;
    }
    if (k == 0 || k == 1) {
        return head;
    }
        
    Node *temp = head;
    int count = 0;
    // 修正循环条件：找当前分组的第k个节点
    while (temp != NULL && count < k - 1) {
        temp = temp->next;
        count++;
    }

    // 如果当前分组不足k个，直接返回原头节点不反转
    if (temp == NULL) {
        return head;
    }

    Node *head2 = temp->next;
    temp->next = NULL;

    Node *newHead = kReverse(head2, k);
    Pair ans = reverse(head);
    ans.tail->next = newHead;
    return ans.head;
}

内容的提问来源于stack exchange，提问作者Divyansh Mehta