206.翻轉(zhuǎn)鏈表

題目描述

給你單鏈表的頭節(jié)點 head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]
輸出：[2,1]

示例 3：

輸入：head = []
輸出：[]

提示：

鏈表中節(jié)點的數(shù)目范圍是 [0, 5000]
-5000 <= Node.val <= 5000

進階：鏈表可以選用迭代或遞歸方式完成反轉(zhuǎn)。你能否用兩種方法解決這道題？

解題思路 & 代碼實現(xiàn)

雙指針法

只需要改變鏈表的 next 指針的指向，直接將鏈表翻轉(zhuǎn)，而不用重新定義一個鏈表。

首先定義一個 cur 指針指向頭節(jié)點，在定義一個 pre 指針初始化為 null

隨后將cur->next節(jié)點用 tmp指針保存一下，隨后將cur -> next指向 pre ，這樣就完成了第一個節(jié)點的翻轉(zhuǎn)。

接下來進入循環(huán)繼續(xù)移動 pre 和 cur 指針，最后 cur指針指向 null ，循環(huán)結(jié)束，鏈表翻轉(zhuǎn)完成，return pre指針， pre指針就指向了頭節(jié)點。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* tmp;ListNode* cur = head;ListNode* pre = NULL;while (cur) {tmp = cur -> next;cur -> next = pre;pre = cur;cur = tmp;}return pre;}
};

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

遞歸法

class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur) {if (cur == NULL) return pre;ListNode* tmp = cur -> next;cur -> next = pre;// 遞歸寫法實際上也是做了這兩步// pre = cur;// cur = tmp;return reverse(cur, tmp);}ListNode* reverseList(LKistNode* head) {return reverse(NULL, head);}
};