題目
題意：反轉一個單鏈表。
示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL
思路
如果再定義一個新的鏈表，實現鏈表元素的反轉，其實這是對內存空間的浪費。
其實只需要改變鏈表的next指針的指向，直接將鏈表反轉 ，而不用重新定義一個新的鏈表，如圖所示:
之前鏈表的頭節點是元素1， 反轉之后頭結點就是元素5 ，這里并沒有添加或者刪除節點，僅僅是改變next指針的方向。
那么接下來看一看是如何反轉的呢？
我們拿有示例中的鏈表來舉例，如動畫所示：（糾正：動畫應該是先移動pre，在移動cur）
首先定義一個cur指針，指向頭結點，再定義一個pre指針，初始化為null。
然后就要開始反轉了，首先要把 cur->next 節點用tmp指針保存一下，也就是保存一下這個節點。
為什么要保存一下這個節點呢，因為接下來要改變 cur->next 的指向了，將cur->next 指向pre ，此時已經反轉了第一個節點了。
接下來，就是循環走如下代碼邏輯了，繼續移動pre和cur指針。
最后，cur 指針已經指向了null，循環結束，鏈表也反轉完畢了。 此時我們return pre指針就可以了，pre指針就指向了新的頭結點。
雙指針法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一個節點
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一個節點，因為接下來要改變cur->next
cur->next = pre; // 翻轉操作
// 更新pre 和 cur指針
pre = cur;
cur = temp;
}
return pre;
}
};
時間復雜度: O(n)
空間復雜度: O(1)
遞歸法
遞歸法相對抽象一些，但是其實和雙指針法是一樣的邏輯，同樣是當cur為空的時候循環結束，不斷將cur指向pre的過程。
關鍵是初始化的地方，可能有的同學會不理解， 可以看到雙指針法中初始化 cur = head，pre = NULL，在遞歸法中可以從如下代碼看出初始化的邏輯也是一樣的，只不過寫法變了。
具體可以看代碼（已經詳細注釋），雙指針法寫出來之后，理解如下遞歸寫法就不難了，代碼邏輯都是一樣的。
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和雙指針法的代碼進行對比，如下遞歸的寫法，其實就是做了這兩步
// pre = cur;
// cur = temp;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 和雙指針法初始化是一樣的邏輯
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};
時間復雜度: O(n), 要遞歸處理鏈表的每個節點
空間復雜度: O(n), 遞歸調用了 n 層棧空間
我們可以發現，上面的遞歸寫法和雙指針法實質上都是從前往后翻轉指針指向，其實還有另外一種與雙指針法不同思路的遞歸寫法：從后往前翻轉指針指向。
具體代碼如下（帶詳細注釋）：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 邊緣條件判斷
if(head == NULL) return NULL;
if (head->next == NULL) return head;
// 遞歸調用，翻轉第二個節點開始往后的鏈表ListNode *last = reverseList(head->next);// 翻轉頭節點與第二個節點的指向head->next->next = head;// 此時的 head 節點為尾節點，next 需要指向 NULLhead->next = NULL;return last;
}
};
時間復雜度: O(n)
空間復雜度: O(n)
Java
// 雙指針
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next;// 保存下一個節點
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
// 遞歸
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一個節點cur.next = prev;// 反轉// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);
}
}
// 從后向前遞歸
class Solution {
ListNode reverseList(ListNode head) {
// 邊緣條件判斷
if(head == null) return null;
if (head.next == null) return head;
// 遞歸調用，翻轉第二個節點開始往后的鏈表ListNode last = reverseList(head.next);// 翻轉頭節點與第二個節點的指向head.next.next = head;// 此時的 head 節點為尾節點，next 需要指向 NULLhead.next = null;return last;
}
}
