链表递归删除是否断链问题


复习数据结构的时候碰到一道题,要求递归删除链表中给定值$$x$$的节点,信手拈来,写了一段代码,和标准答案一比对,头顶出现一个大大的问号,标准答案的代码不会导致断链吗?
标准答案如下:

void delete(LinkList& L, ElemType x) {
    if (L == NULL) {
        return;
    }
    if (L -> data == x) {
        LNode* p = L;
        L = L -> next;  // 不用访问前驱节点,怎么做到不断链的删除节点
        free(p);
        delete(L, x);
    }
    else {
        delete(L -> next, x);
    }
}

不会断链原因

由于函数参数是传引用,每次传过去的是节点的地址,画一下递归栈就可以很好理解了:
比如单链表 2 -> 4 -> 5,$$L$$ 指向头节点。
执行 $$delete(L, 4);$$

递归栈如下:
递归栈

结合代码理解

if (L -> data == x) {
    LNode* p = L;
    L = L -> next;  // L -> next = L -> next -> next
    free(p);
    delete(L, x);
}

栈中第二个参数 L -> next 带入,原本会断链的语句现在变成了L -> next = L -> next -> next,明显是正确的,成功删除了指定节点且没有断链。

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 链表递归删除是否断链问题


Just For Fun...