關于這道題，總的來說有兩類方法：迭代和遞回，
先來介紹迭代，遞回的思路要在迭代上延申，
常見的
三指標法
思路
用一個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;
}
這題加深我對遞回與鏈表的理解，希望每一個看到的人都能對遞回與鏈表有更深的理解，
感謝觀看，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274169.html
標籤：其他
上一篇：SQL注入繞過WAF兩道題目
下一篇：2021.4.8