如何用递归将链表偶数节点移至另一链表？代码异常排查

核心问题梳理 #

你的代码存在多个逻辑错误，导致迁移结果异常：

• 指针传递方式错误：newnode按值传递，递归中修改的是局部副本，外层指针完全不受影响，新链表的节点无法正确串联。
• 偶数节点判断逻辑错误：用length(temp) % 2 == 0判断完全不合理——length(temp)是计算当前temp到链表尾的长度，和节点在原链表中的位置无关。比如原链表nor->us->while->ok，第一个temp是nor，长度为4，会触发逻辑，但第二个temp是us，长度为3，不会触发，导致后续偶数节点被遗漏。
• 新链表构建逻辑混乱：else分支中创建新节点后直接将newnode指向newnode->next（空指针），刚创建的节点直接丢失，无法形成有效链表。
• 初始节点错误：外层函数中提前创建空的newnode，会导致链表A开头出现无数据的空节点。
• 原链表节点移除不完整：第一个偶数节点处理时未修改原链表的指针，导致原链表节点未被正确移除。

修复后的代码 #

我们改用直接操作原链表的偶数位置节点（第2、4...个），同时用指针引用传递维护新链表的尾部，确保递归中能正确构建链表：

完整修复代码 #

// 递归辅助函数：curr为原链表当前的奇数位置节点，newListTail为新链表A的尾节点（引用传递）
void moveAlternativeRecursive(node<string>*& curr, node<string>*& newListTail) {
    // 终止条件：当前节点为空，或当前节点没有下一个节点（无偶数节点可处理）
    if (curr == nullptr || curr->next == nullptr) {
        return;
    }

    // 取出当前要迁移的偶数节点（curr的下一个节点就是偶数位置）
    node<string>* evenNode = curr->next;
    // 从原链表中移除这个偶数节点
    curr->next = evenNode->next;

    // 将偶数节点添加到链表A中
    if (A.head == nullptr) {
        // 链表A为空，设置头节点
        A.head = evenNode;
        newListTail = evenNode;
    } else {
        // 链表A已有节点，追加到尾部
        newListTail->next = evenNode;
        newListTail = evenNode;
    }
    evenNode->next = nullptr; // 断开原链表的链接，避免循环

    // 递归处理原链表的下一个奇数节点
    moveAlternativeRecursive(curr->next, newListTail);
}

// 对外调用的入口函数
void movealternative() {
    // 初始化链表A的头节点为空
    A.head = nullptr;
    node<string>* newListTail = nullptr;
    // 从原链表的头节点开始递归处理
    moveAlternativeRecursive(pass.head, newListTail);
    // 输出链表A
    A.print();
}

代码说明 #

1. 指针引用传递：curr用引用传递，确保递归中修改原链表的指针能直接生效；newListTail用引用传递，方便维护新链表的尾部，避免每次遍历找尾的开销。
2. 精准定位偶数节点：直接将curr->next作为要迁移的偶数节点（原链表第2、4...个节点），逻辑清晰准确。
3. 正确维护链表结构：移除原链表节点时，将curr->next指向偶数节点的下一个节点；添加到新链表时，要么设置头节点，要么追加到尾部，同时断开偶数节点的原链接，避免链表循环。
4. 无冗余空节点：初始化时A.head设为nullptr，只有当第一个偶数节点被迁移时才设置头指针，避免空数据节点。

测试验证 #

对于原链表nor->us->while->ok：

1. 第一次递归处理nor，迁移us到链表A，原链表变为nor->while->ok；
2. 第二次递归处理while，迁移ok到链表A，原链表变为nor->while；
3. 最终链表A输出us->ok，符合预期。

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