逆向单向链表（单向链表的逆转）



最近在看链表，今天刷到一道链表的反转题，链表反转可以说是基础操作，但是可提供的方案也有很多，简单通过了该题后又学习了一下递归反转，现在把三种方法都公开出来做一个总结。

1.就地逆置

2.单参数的递归逆置

3.双参数的递归逆置

一、就地逆置

方法：头插。

由于这里是不带表头结点的单向链表，所以头插会稍微复杂一点，不想往下看的小伙伴也可以直接选择定义一个临时表头结点从头结点开始遍历链表将每一个链表头插，最后将头结点指向表头结点的next指针域，最后free掉那个表头结点即可。

虽然不带表头结点头插会稍微复杂一些，但是只要加一条语句就可以解决问题。

在不带表头结点的单向链表中进行头插，唯一要特殊处理的地方就是头结点。而中间结点和尾结点的头插可以简化为下面的代码段

pre->next = head;

head = pre;

在找到普遍规律后，接下来就要考虑特殊情况是否能适应普遍规律。在这里如果pre指向链表头结点，pre->next = head;则产生一个环，导致的结果就是在链表遍历结束后，尾部会产生一个长度为1的环。

而我们想要的尾部应该是指向NULL的，所以很显然，if pre == head, pre->next = NULL; 为了使代码更加美观具有统一性，所以我们增设一个指针 q，初始值为NULL即可。

代码如下

------------------------以下为9.6号补充-----------------

上面这段就地逆置代码本质上为创建链表，下面给出同等效果的另一种形式。（这种形式将节省一个指针p的空间，并用head来代替p遍历链表，用h1指针指向所创建新链的头结点，这种形式更加突出的体现了以建链来逆置链表的思想）

至于选用哪种方法依个人爱好即可，这里只是贴出来发散一下思维。

---------------------------end---------------------------------

二、单参数递归逆置

　　如果单向链表可以从后向前遍历，那我想要逆置链表不就变得容易的多，只需要从尾结点开始不断的让尾结点指向前一个结点即可。

　　但事实上单向链表只能单向遍历，如果想要直接逆向遍历是几乎不可能的，但是递归间接的帮我们实现了这个功能。

　　先摆一下函数声明

　　ElemSN *ReverseList(ElemSN *head);

　　递归无非就是自己调用自己，理解递归其实很容易，在递归里，ReverseList函数每调用自己一次，都相当于将该函数全部代码粘贴到函数调用处一次，直到某次调用自己时触发了return 返回，然后不断的返回返回，直到返回到第一次调用，最终返回一个结果值。

　　因此看一个简单的递归函数

该函数通过不断调用自己实现对链表的遍历，并且该函数将head->next == NULL作为函数第一次的返回点，也就是当形参head到达尾结点时开始返回，之后每次返回都会将该结点传至上一层调用，直至到达最顶层调用时返回尾结点。

可见递归，从最顶层开始逐级调用自己的过程是从头到尾遍历链表的过程，而从最底层调用开始逐级返回则是一个由尾到头遍历链表的过程。而我们要做的逆置操作就从函数逐级返回开始，因此我们就可以利用这一特性写出下面的递归逆置代码

三、双参数递归逆置

　　从上一个方法中了解到递归逆置无非就是在逐级返回这个过程中 不断让后一个结点指向前一个结点。

　　那我们显然可以直接将前后结点作为函数形参在递归过程中依次遍历链表，当后结点到达尾结点时，开始逐级返回并让后结点的next指向前结点，当然这里需要记得在函数返回时传递尾结点（逆置后的头结点）

代码如下

在这个函数中不用担心会在尾部生成一个环，递归，从哪里开始，最终又会回到哪里，所以在调用该函数时 可以使用 head = ReverseList(head, NULL);的语句，这样子，函数的起点状态将是 ,ptr = head, pre = NULL,最终也会是这个状态，所以 在最后一次返回该函数时

ptr->next = pre;相当于我们传进去的头指针next指向了NULL，这样逆置后的链表尾部自然就是NULL了。

--------------------------------------以下为9.6号补充------------------------------

再次回顾该代码时，发现函数的第一次返回点和函数逐级返回时的语句有重复的地方，再次思考后发现该重复点可以合并，于是就产生了下面的代码。（两处分别是 return ptr;和return reverseNode;的上一条语句 ptr->next = pre;）

--------------------------------------------end-----------------------------------------

End。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/15149.html