C语言递归逆向输出单链表反转 递归最后一个数值为什么这么大

来源：蜘蛛抓取(WebSpider) 时间：2018-10-02 12:37 标签： 单链表反转 递归

假设每一个node的结构是：

因为在对链表进行反转的时候，需要更新每一个node的“next”值，但是，在更新 next 的值前，我们需要保存 next 的值，否则我们无法继续。所以，我们需要两个指针分别指向前一个节点和后一个节点，每次做完当前节点“next”值更新后，把两个节点往下移，直到到达最后节点。

上面代码使用的是非递归方式，这个问题也可以通过递归的方式解决。代码如下：

递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 (代码倒数第二句)。 在上面的代码中， reverseRest 的值没有改变，为该链表的最后一个node，所以，反转后，我们可以得到新链表的head。


/*链表节点存储的数据*/ /*递归实现反转不带头节点的单向链表 visit 自定义节点访问函数 { /*返回当前节点指针，次种情况只有在当前节点为尾节点时才能执行到*/ else /*其他节点的情况，先调用递归函数反转后续节点，再反转当前节点*/ { /*并将递归函数返回来的尾节点指针向上层函数返回*/ /*自定义链表节点访问函数*/ /*用键盘输入初始化一个链表，参数为链表头指针地址*/ /*开始构造不带头节点的单向链表*/ if(i==1) /*如果当前输入的是第一个节点，则让头指针指向它*/

把问题规模减小，并且减小的量为1

假设我们的程序能够正常的反转：则反转后为

反转后，1元素并没有任何操作，所以反转1的next仍然指向2，

假设2开头的链表已经反转成功，接下来只要将2的next指向1，

看似复杂的问题，把如此多的指针反过来指，其实只要将两个节点反过来即可。

* head为待反转链表的头结点 * @return 反转后的链表头结点，当然该链表也是以null结尾 //把上两个特殊情况合起来 //假设函数能够反转链表，返回头结点 //此时如图4状态，1的getNext就是第二个结点2， //把第二结点2的next指向head则实现把2的指针指向1，如图5 //取出传入数据的第一个结点 //取走一个元素后，从第二个元素创建一个链表， //因为返回的是Node，所以用Node来接收 //假设传入来的List有一个元素，则走到这里时sublist传入的两个参数相等 //与我们期望返回值一致 // //第一个结点的next指向规模缩小的链表返回来的头结点 //上面两行代码清理成如下代码


我要回帖

更多关于 单链表反转 递归 的文章

 

随机推荐