反轉(zhuǎn)鏈表
力扣題目鏈接
題目描述
給你單鏈表的頭節(jié)點(diǎn)
head，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
思路
面試?？嫉念}型，這里帶來(lái)兩種做法，一種雙指針，一種迭代法。
雙指針法
第一次看到題目時(shí)，我第一時(shí)間想到的是，先從第一個(gè)結(jié)點(diǎn)找到最后一個(gè)，然后再依次翻轉(zhuǎn)。但是這樣的時(shí)間復(fù)雜度就是O（2n）了。
為什么不能第一次遍歷的時(shí)候就處理好所有翻轉(zhuǎn)呢？定義兩個(gè)指針
- pre：指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
- cur：指向當(dāng)前結(jié)點(diǎn)
這樣這需要一對(duì)對(duì)處理即可，難點(diǎn)在于如何進(jìn)行結(jié)點(diǎn)的更替。
代碼如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-568460.html
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tmp;
ListNode* cur = head;
ListNode* pre = nullptr; //頭節(jié)點(diǎn)的pre指向null
while(cur){
tmp = cur->next; //保存cur的下一個(gè)結(jié)點(diǎn)，因?yàn)橄乱徊揭薷?/span>
cur->next = pre;
//update
pre = cur; // 更新結(jié)點(diǎn)，從后往前更新
cur = tmp;
}
return pre;
}
};
- 時(shí)間復(fù)雜度：O（n）
- 空間復(fù)雜度：O（1）
迭代法
迭代法的本質(zhì)思路其實(shí)跟雙指針是一樣的，不同點(diǎn)在于使用了n棧的空間。
如果可以理解雙指針，理解迭代法應(yīng)該是更加輕松才對(duì)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-568460.html
代碼如下：
ListNode* reverseList(ListNode* head) {
return reverse(nullptr,head);
}
ListNode* reverse(ListNode* pre, ListNode* cur)
{
if(cur == nullptr)return pre; //終止條件
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur,tmp);
}
- 時(shí)間復(fù)雜度：O（n）
- 空間復(fù)雜度：O（n）
到了這里，關(guān)于day4-反轉(zhuǎn)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
