單鏈表的反轉（面試常出）：

? 單鏈表的反轉，可以通過很多種方法實現。包括迭代法，遞歸法，

• 迭代法：

  1. 定義三個指針：prev、current和next，它們分別表示前一個節點、當前節點和下一個節點。

  2. 初始化時，prev為null，current為頭節點。

  3. 在循環中，不斷將current的next指針指向prev，然后依次向后移動prev、current和next指針。

  4. 當next為空時，說明已經到達鏈表末尾，此時的prev指向就是反轉后的頭節點。

  其實就像是先將第一個節點指向null，就像最后一個節點它也是next = null的；然后一直這樣子重復，轉一次就后退，讓下一個節點去轉方向指向前面的。

  

  public ListNode reverse(Node head) {Node prev = null;Node current = head;while (current != null) {Node nextTemp = current.next; // 暫存當前節點的下一個節點current.next = prev; // 將當前節點指向前一個節點prev = current; // 更新prev為當前節點current = nextTemp; // 更新current為原先的下一個節點}return prev; // 返回反轉后的頭節點}
  

  // 補充一個力扣第92題，加深理解（讓你把單鏈表部分元素反轉，其他部分不變）

• 

? 這里依舊可以使用迭代的方法，就是要先通過遍歷去找到反轉開始的位置和結束的位置；用輔助節點記錄反轉區間的前置節點和反轉區間的尾節點。然后反轉區間的鏈表反轉即可，反轉后接上前面的部分。

public ListNode reverseBetween(ListNode head, int left, int right) {ListNode current = head;ListNode prev = null;for (int i = 1; i < left; i++) {prev = current;current = current.next;}// 反轉區間的前置節點ListNode tailPrev = prev;// 反轉區間的尾節點ListNode tail = current;// 同樣的迭代原理，只是范圍要自定義。for (int j = left; j <= right; j++) {ListNode newTemp = current.next;current.next = prev;prev = current;current = newTemp;}// 反轉區間的頭節點ListNode headReverse = prev;tail.next = current;if (tailPrev != null) {tailPrev.next = headReverse;return head;} else {return headReverse;}
}

遞歸法：（也是力扣第206題）

? 遞歸的關鍵是看整體，找出整體的大塊東西。可以先寫一個偽代碼過一遍思路。你就寫基礎情況，然后要的操作，再看子問題（遞歸調用）放的位置即可。

**實操技巧：**第一步先找到可以看作整體的，就是原理一樣的。去設計遞歸調用（超級操作），第二步去設計微操作，去看一份整體的怎么實現即可。后面就去找到題目中的基礎情況，它相當于最里面的超級操作了，也基本就是剩下一個的情況那種。

相關概念：

? 1.首先先明確函數的意義，還要原問題和子問題。在這里原問題是給整個鏈表反轉，子問題是給每一個字節進行反轉。

? 2.基礎情況，也就是要找到結束的條件。就是當數據規模很小的時候，能結束遞歸，返回答案。

? 3.遞歸調用（超級操作），怎么搞定中間的遞歸操作。但是！唉！人腦進去遞歸出不來的。所以得完把遞歸的過程看成一個整體，不要去想里面怎么運行的。

? 4.微操作。也就是操作的方法。

? 比如漢諾塔問題，你有2個疊在一起的時候，就是先把小的放中間，大的放右邊，再把小的放大的上面。那這個時候，假如他有一堆，你就是把小的一堆給放到中間，讓最大的去到最右邊墊底。然后小的一堆整體放到大的上面。而那一堆小的移動其實就是整個問題的子問題，它其實就是可以用遞歸重復一個原理完成。

此題思路如下：

// 定義：輸入一個單鏈表頭結點，將該鏈表反轉，返回新的頭結點
ListNode reverse(ListNode head) {// 基礎情況，也就是結束的代碼。// 鏈表為空或者只有一個節點時，直接返回頭節點即可。if (head == null || head.next == null) {return head;}// 遞歸調用（超級操作）ListNode last = reverse(head.next);// 而其實當你寫一個偽代碼時候，你也可以發現。下面的這個其實就是反轉需要的的操作，可以寫一個偽代碼，微操作。具體操作方法： operate(head.next); head.next.next = head;head.next = null;return last;
}