问题的由来：
当你第一次实现用递归实现链表删除功能的时候，是否有一丝丝的考虑过。这个问题呢？为什么对于非递归版本的删除必须要知道当前要删除节点的前驱，而需要对其前驱节点的next域指针进行修改。而递归删除却不需要呢?难道这样不会造成链表的断链吗？
好了。我们开始抽象出我们今天要解决的问题。
问题一：
递归实现链表节点的删除和非递归删除的区别是什么？
问题二:
为什么在使用递归删除的时候链表不会断链？
先给个代码，好根据代码模拟，不会空想。
函数的递归模型：
终止条件：f(L,x)=不做任何事若L为空表
递归主体:f(L,x)=删除*L结点;f(L-next,x);若L-data==x
f(L,x)=f(L-next,x);其他情况
/*用递归实现对没有头结点的链表实现删除给定数字输出最终结果*/typedefintElemType;constintMaxSize=;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;//递归删除链表节点函数voidDel_X_3(LinkListL,ElemTypex){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);}
先解决问题一：
对于非递归版本的删除链表结点，必须要知道其前驱结点。假设当前要删除的结点为p,前驱结点为q。修改代码如下：q-next=p-next;而从上面的代码可以看出，对于递归版本的程序并不需要特别的知道其前驱结点。
再解决问题二：
首先，我们要先明确一个问题。就是上面给出的程序是用引用的。这说明了函数是传址调用。这就是当删除一个结点时候，不用需要知道前驱结点也可以的根本所在。
给个例子模拟一下你就知道了:
3//输入三个数
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条件满足为止，然后开始递归返回值。最后终止。
而这个过程是传址的。所以，这回影响最终的结果。
带返回值的递归
structListNode*removeElements(structListNode*head,intval){if(head==NULL){returnNULL;}/*删除原链表中头节点后面值为val的元素的节点*/structListNode*res=removeElements(head-next,val);/*原链表头节点也是要删除的节点*/if(head-val==val){returnres;/*原链表头节点不是要删除的节点，将原链表中头节点后面挂接的更短的链表已删除值为val的节点的链表挂接在原链表的头节点后面*/}else{head-next=res;returnhead;}}
链表反转递归
/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*reverseList(structListNode*head){if(head==NULL
head-next==NULL){returnhead;}structListNode*res=reverseList(head-next);head-next-next=head;head-next=NULL;returnres;}
从末尾到头打印链表递归
/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode(intx):val(x),next(NULL){}*};*/classSolution{public:vectorintreversePrint(ListNode*head){if(!head)return{};vectorintpre=reversePrint(head-next);pre.push_back(head-val);returnpre;}};预览时标签不可点收录于话题#个上一篇下一篇