©2020-2024 ioDraw All rights reserved,
Privacy Policy
关于这道题，总的来说有两类方法：迭代和递归。
先来介绍迭代，递归的思路要在迭代上延申。
常见的
<>三指针法
思路
用一个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; }
这题加深我对递归与链表的理解，希望每一个看到的人都能对递归与链表有更深的理解。
感谢观看。