反轉(zhuǎn)一個(gè)單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
這題用迭代的思路非常簡(jiǎn)單稠诲，有很多種思路诡曙，可以直接頭插臀叙，可以直接一個(gè)個(gè)去改變指針指向价卤，復(fù)雜度都是O(N)，可以說是比較簡(jiǎn)單高效的算法了都床嫌。但是這題用遞歸的話就要費(fèi)點(diǎn)心思了跨释。
這題想要遞歸厌处，那么我們需要清楚這個(gè)遞歸肯定是從頭結(jié)點(diǎn)開始一直遞歸到尾結(jié)點(diǎn)
- 1、先要確定終止條件阔涉。
如果是一個(gè)節(jié)點(diǎn)或者沒有節(jié)點(diǎn)，那么反轉(zhuǎn)就是其本身贯要。 - 2、確定在遞歸過程中需要做什么崇渗。
我們的目的其實(shí)很簡(jiǎn)單表面上
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
但是其實(shí)是
輸入: 1->2->3->4->5->NULL
輸出: NULL<-1<-2<-3<-4<-5
修改指針指向的位置函荣。
我們以2這個(gè)節(jié)點(diǎn)為例子，我們要修改他的下一個(gè)節(jié)點(diǎn)不再是3傻挂，而是2。3也是這樣要修改他的下一個(gè)節(jié)點(diǎn)不再是4兽肤，而是2绪抛。
-3心剥、注意點(diǎn)
我們要注意頭和尾的處理
這里的原本的尾部是5，我們要讓他指向4，這個(gè)沒有其他的處理惶看，但是原本的頭部1阵子，我們要進(jìn)行處理將其指向NULL贞铣。
經(jīng)過分析后代碼
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL){
return head;
}
ListNode *p=reverseList(head->next);//p是我們要返回的節(jié)點(diǎn)，一直遍歷到遞歸終止我們可以得到的是5節(jié)點(diǎn)
head->next->next=head;//我們進(jìn)行修改辕坝，head此時(shí)是4為例，4的原本下一個(gè)節(jié)點(diǎn)是5,5的下一個(gè)節(jié)點(diǎn)修改為4，形成反置
head->next=NULL;//最后再把4節(jié)點(diǎn)的下一個(gè)置為空江场，反正返回到上一層會(huì)重新置為3挚歧，這一步是針對(duì)頭結(jié)點(diǎn)的吁峻。
return p;
}
};
