关于这道题,总的来说有两类方法:迭代和递归。
先来介绍迭代,递归的思路要在迭代上延申。
常见的

<>三指针法

思路
用一个cur指针来定位目前遍历的结点的位置。
一个pre指针来记录上一个结点的位置,为了可以对目前结点的指向进行反转。
用一个指针last来保存下一个结点的位置,可以保证目前结点的指针转向后,可以继续遍历。
这样一次遍历就足够完成反转,且只创建了三个指针空间。时间复杂度O(n),空间复杂度O(1)。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* pre =
NULL, * cur = head; struct ListNode* last; while (cur != NULL) { last = cur->
next; cur->next = pre; pre = cur; cur = last; } return pre; }

就这样依次移动当cur走到NULL时,循环结束,且,pre也已经移动到前一个位置,也就是

cur与last都指向NULL。pre就变成了头结点(不是哨兵位)返回。

同时,也是当head->next== NULL或这head==NULL时,也就是链表只有一个结点或者为空表时,也同样成立。

诺链表为空,根本不会进循环,直接返回pre空指针。

诺链表只有一个结点时,也只会循环一次,cur指向NULL,而pre指向该结点。

<>头插法

利用链表结点头插法。

如果所有结点以头插法,形成链表,最终打印时会顺序输入,倒序打印。

就是利用这个性质,对链表进行修改,反转。(我看到这真是感叹算法实在太强了)。还不用开辟空间。

由于链表不能随机访问,只能依次每个结点进行遍历,所以要利用这一点。
可以考虑,每遍历一个结点,都可将该结点看为头结点。

对于1,要满足题目,则是5->4->3->2->1->NULL

先假想头插法延长链表
依次开辟空间,同时设为头结点,再开辟的新空间的指针都指向头结点。
就根据这个算法,对链表进行操作。

先将phead指针指向NULL,因为将第一个结点带入循环中,这并不是第一个特殊结点,而是相当于是中间的某个结点,新指向的结点都要指向头结点,这样才会满足头插法。同时当循环结束时,链表末尾就是一个NULL。

总结一下,
一个指针依次指向一个结点,其结点都要满足,cur->next指向头节点。
同时再下一次循环开始时,该结点要成为头结点,这样,才满足,链表只是反转指针方向。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* phead =
NULL; struct ListNode* cur = head; while (cur) { struct ListNode* la = cur->next
; cur->next = phead; phead = cur; cur = la; } return phead; }

在每一次按照原链表去遍历的时候,都要保证可以让cur指针依次指向下一个结点。用一个指针去报存下一个结点的位置。设置好头结点后,cur就要去提取下一个结点(相当于头插法创建链表时的添加结点)。
这样的方法相当快了

<>递归

递归一直是个让我头痛且死脑细胞的方法。
总结一下,可以使用递归的三个条件:

* 能将一个问题转变成一个新的问题,而新问题与原问题的解法要相同或类同,不同的仅仅是处理的对象,而且这些对象要逐次变小且有规律的变化。
* 可以通过上述不断转化而使问题简化成一个个简单且类似的问题。
* 必需要有一个递归出口或者边界
(套娃得有限度)

递归“分治法”
void p(参数表) { if(递归结束条件/递归出口) 直接求解//递归终止条件 else p(较小的参数)//递归入口,步骤
将大问题一次一次简化成有限个小问题去依次解决

先想想如果只有一个结点的链表怎么处理

那就不处理cur->next指向NULL的结点,直接返回。

如果是只有两个结点的链表呢?

head结点就是1,然后要将1指向的结点2的next指向结点1,然后要将1结点的next指向NULL。对于2结点不处理,但要返回2结点的位置,是新的头结点。
那3个,4个,5个…结点的链表呢?

这就是一个套娃。设每个cur都是头指针,每次对归到哪个结点,该节点都是头指针。

从第一个指针开始递归,直到遇到一个结点的next指向NULL。就返回或者说回到上一个递归结点处。对最后一个结点是不进行任何操作,同时还要返回最后一个结点的地址。
每个头指针和后面的结点都可以看成两个结点的模式,只对其下一个结点进行指针逆转。
这就与迭代的头插法相似,只对两个结点进行逆转指针操作。每次递归都是寻找下一个头结点。

每次递归结束,都是对这head与下一个结点,这两个结点进行指针逆转。
无论链表结点有多少,我都可以通过递归将其转换成两个结点的链表,并对其反转。
struct ListNode* reverseList(struct ListNode* head) { if(head==NULL||head->next
==NULL)//要先保证head不为空再head->next结束递归并返回head的有效地址 return head; struct ListNode*
phead=reverseList(head->next); head->next->next=head; head->next=NULL; return
phead; }
这题加深我对递归与链表的理解,希望每一个看到的人都能对递归与链表有更深的理解。

感谢观看。

技术
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信