问题的由来：
当你第一次实现用递归实现链表删除功能的时候，是否有一丝丝的考虑过。这个问题呢？为什么对于非递归版本的删除必须要知道当前要删除节点的前驱，而需要对其前驱节点的next域指针进行修改。而递归删除却不需要呢?难道这样不会造成链表的断链吗？
好了。我们开始抽象出我们今天要解决的问题。
问题一：
递归实现链表节点的删除和非递归删除的区别是什么？
问题二:
为什么在使用递归删除的时候链表不会断链？
先给个代码，好根据代码模拟，不会空想。
函数的递归模型：
终止条件： f(L,x) = 不做任何事 若L为空表
递归主体: f(L,x) = 删除*L结点;f(L->next,x); 若L->data == x
f(L,x) = f(L->next,x); 其他情况
/*用递归实现对没有头结点的链表实现删除给定数字输出最终结果*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cstdlib>using namespace std;typedef int ElemType;const int MaxSize = 100;typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;//递归删除链表节点函数void Del_X_3(LinkList &L,ElemType x) {LNode *p;if(L == NULL) {return;}if(L->data == x) {p = L;L = L->next;free(p);Del_X_3(L,x);//printf("if2–> %d\n",L->data);} else {Del_X_3(L->next,x);//printf("else–> %d\n",L->data);}//printf("—>%d\n",L->data);}int main(int argc,char **agrv) {int n;while(~scanf("%d",&n)) {int x;LinkList L = NULL;LNode *s, *r = L;for(int i = 0;i < n;++i) {scanf("%d",&x);s = (LNode *)malloc(sizeof(LNode));s->data = x;if(L == NULL) L = s;else r->next = s;r = s;//printf("–>%u\n",r);}r->next = NULL;printf("Please enter you want to delete number: ");scanf("%d",&x);LNode *p = L;while(p) {printf("%ox ",p);p = p->next;}puts("");Del_X_3(L,x);////testp = L;while(p) {printf("%ox %d\n",p,p->data);p = p->next;}puts("");}return 0;}先解决问题一：
对于非递归版本的删除链表结点，必须要知道其前驱结点。假设当前要删除的结点为p,前驱结点为q。修改代码如下：q->next = p->next;而从上面的代码可以看出，对于递归版本的程序并不需要特别的知道其前驱结点。
再解决问题二：
首先，我们要先明确一个问题。就是上面给出的程序是用引用的。这说明了函数是传址调用。这就是当删除一个结点时候，不用需要知道前驱结点也可以的根本所在。
给个例子模拟一下你就知道了:
3 //输入三个数
3 4 5
4 //删除4
模拟函数调用过程：
初始链表逻辑关系：3 –> 4 –> 5
1、从3结点开始： f(&L,4) —-> 这时候明显不是要删除的数。
所以调用else部分。
L1->next引用传址。（当前的L表示的是结点3）
2、4结点开始： f(&L,4) —–> 这时候发现4就是要删除的数。
调用if2部分
处理代码为:L2 = L2->next（发现问题吗？）
（L1和L2同表示L，为了好说明特别加以区别加了下标。）
其实，L2 == L1->next（即L1->next为结点3的next域）
而执行L2= L2->next现在就相当于把3的next域指向了5 的指针域。(L1->next = L2->next。所以，我们在这个 删除的过程中还是隐含的知道了要删除结点的前驱结点)
即，现在的逻辑关系变为：3->5
后面的就都一样了，就不在详说了。程序一直执行到if1 条件满足为止，然后开始递归返回值。最后终止。
而这个过程是传址的。所以，这回影响最终的结果。
好了。两个问题都完美解决了。虽然，问题不是什么难题。但是，如果对语言和递归没有深刻的掌握还是一时难以理解的。
，可见内心底对旅行是多么的淡漠。
