如何用单个递归函数从无限双向链表中间搜索指定键？

原代码的核心问题 #

1. 无终止搜索的标记机制：即使找到目标键，后续递归仍会持续执行，而无限链表会导致递归无限进行，最终栈溢出。key = 0; 是传值修改，无法通知上层递归停止搜索。
2. 无效判断：代码中head变量未定义，属于冗余逻辑，应移除。

修改后的递归实现 #

通过添加一个引用类型的标记，实现单次递归同时搜索左右两侧，且找到目标后立即终止所有递归：

template <typename T>
void searchMiddle(Node<T>* middle, int key, int index, bool& found) {
    // 已找到目标或当前节点为空，直接返回
    if (found || middle == nullptr) {
        return;
    }

    // 检查当前节点是否匹配目标键
    if (middle->data == key) {
        cout << "key found at index " << index << endl;
        found = true; // 标记已找到，终止所有后续递归
        return;
    }

    // 先递归搜索左侧（prev方向）
    searchMiddle(middle->prev, key, index - 1, found);
    // 左侧未找到时，再递归搜索右侧（next方向）
    if (!found) {
        searchMiddle(middle->next, key, index + 1, found);
    }
}

调用方式 #

需要初始化一个布尔标记变量，用于传递“是否找到”的状态：

bool found = false;
// 假设middleNode是链表中间节点指针，targetKey是要搜索的键
searchMiddle(middleNode, targetKey, 0, found);

注意事项 #

• 若目标键不存在于无限链表中，递归会无限执行并导致栈溢出，实际场景中需添加递归深度限制，或改用迭代方式实现。
• 引用参数found用于在所有递归分支间共享状态，确保找到目标后立即停止所有搜索流程。

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