复习数据结构的时候碰到一道题,要求递归删除链表中给定值$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,明显是正确的,成功删除了指定节点且没有断链。
Comments | NOTHING