C++递归复制双向链表函数运行异常,结果末尾多出0节点如何解决
错误原因梳理
- 无前置终止判断,盲目申请节点:函数进入后未先判断入参
head是否为NULL,就直接new了一个默认构造的节点。当递归到原链表最后一个节点的_next(即NULL)时,依然会创建一个值为T()(int类型下默认值为0)的空节点,这就是末尾多出来的0节点的来源。 - 逻辑冗余且未覆盖所有返回分支:代码中写的
while循环完全无效,循环体第一趟执行就会直接return,不会进入第二次循环;同时当head为NULL时,函数没有显式返回值,属于C++未定义行为,实际运行时刚好返回了提前创建的空节点,才导致多余节点被接入链表。 - 未处理双向链表的
_prev指针:当前实现只赋值了_next指针,复制出的链表所有节点的_prev都为默认的NULL,不满足双向链表的结构要求。
修复后的实现
template <typename T> node<T>* _copy_list(node<T>* head) { // 递归终止条件:传入节点为空直接返回NULL,不创建新节点 if (head == NULL) { return NULL; } // 仅当head不为空时,创建对应复制节点 node<T>* copy = new node<T>(head->_item); // 递归复制后续链表 copy->_next = _copy_list(head->_next); // 处理双向链表的前驱指针:如果后续节点存在,将其前驱指向当前复制节点 if (copy->_next != NULL) { copy->_next->_prev = copy; } return copy; }
修复说明
- 新增了递归终止判断,传入空指针时直接返回NULL,不会额外创建默认节点,解决了末尾多0的问题
- 删除了无效的
while循环,递归逻辑本身就完成了全链表遍历 - 补充了
_prev指针的赋值逻辑,保证复制后的链表是完整的双向链表 - 所有分支都有显式返回值,避免了未定义行为
内容的提问来源于stack exchange,提问作者TeachMeTWz
相关产品推荐
相关产品推荐

