206.反轉鏈表
給你單鏈表的頭節點?head?，請你反轉鏈表，并返回反轉后的鏈表。
示例 1：
輸入：head = [1,2,3,4,5] 輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2] 輸出：[2,1]
示例 3：
輸入：head = [] 輸出：[]
提示：
- 鏈表中節點的數目范圍是?
[0, 5000] -5000 <= Node.val <= 5000
反轉鏈表通常有兩種方法：迭代法和遞歸法。
迭代法（雙指針）
????????假設原來的鏈表是1->2->3->4->5->null，反轉后變成null<-1<-2<-3<-4<-5。那在迭代的時候，初始狀態應該是prev=null，current=head。然后循環處理每個節點：????????????????????????
????????在循環中，首先保存當前節點的下一個節點nextTemp，然后把當前節點的next指向prev。接著prev移動到current的位置，current移動到nextTemp的位置。直到current為null，此時prev就是新的頭節點。
實現代碼：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode current = head;ListNode prev = null;while (current != null) {ListNode nextTemp = current.next; // 保存下一個節點current.next = prev; /// 反轉指針prev = current; // 前移prevcurrent = nextTemp; // 前移current}return prev; // prev即為新鏈表的頭結點}
}步驟解釋：
-
初始化指針：使用兩個指針
prev和current，初始時prev為null，current指向頭節點head。 -
遍歷鏈表：在
current不為null時循環處理每個節點。-
保存下一個節點：臨時存儲
current.next到nextTemp，防止反轉指針后丟失后續節點。 -
反轉指針：將當前節點
current的next指向prev，完成當前節點的反轉。 -
移動指針：將
prev移動到當前current的位置，current移動到之前保存的nextTemp位置。
-
-
返回新頭節點：當循環結束時，
current為null，prev指向原鏈表的最后一個節點，即反轉后的新頭節點。
遞歸法
遞歸方法的步驟如下：
- 遞歸終止條件：當前節點為空或下一個子節點為空，返回當前節點
- 遞歸反轉后續鏈表，得到反轉后的頭結點
- 將當前節點的下一個節點的next指向當前節點，形成反轉
- 將當前節點的next設為null，斷開原來的連接
- 返回反轉后的頭結點
實現代碼
class Solution {public ListNode reverseList(ListNode head) {// 遞歸法// 遞歸終止條件，空鏈表或單鏈表無需反轉if (head == null || head.next == null) {return head;}// 遞歸反轉后續鏈表，得到新頭結點ListNode newHead = reverseList(head.next);// 調整指針方向，將當前節點的下一個節點的next指向自己head.next.next = head;// 斷開當前節點的原指向，防止循環head.next = null;// 返回新頭結點return newHead;}
}示例分析
1. 遞歸調用棧展開
遞歸從頭部節點?1?開始，逐層深入，直到鏈表末尾的節點?5。以下是調用棧的展開過程：
reverseList(1) → reverseList(2) → reverseList(3) → reverseList(4) → reverseList(5)
終止條件觸發：當調用?reverseList(5)?時，5.next == null，直接返回?5（此時?newHead = 5）。
2. 遞歸回溯與指針調整
遞歸開始逐層回溯，每層處理當前節點并調整指針方向：
層 4（head = 4）
-
輸入鏈表狀態：
4 → 5 -
操作步驟：
-
收到下層返回的?
newHead = 5。 -
調整指針：
4.next.next = 4?→?5.next = 4（形成?5 → 4）。 -
斷開原鏈：
4.next = null（防止?4 → 5?循環）。
-
-
輸出鏈表狀態：
5 → 4 → null -
返回：
newHead = 5
層 3（head = 3）
-
輸入鏈表狀態：
3 → 4 → null（原鏈未修改時，3.next?仍指向?4）。 -
操作步驟：
-
收到下層返回的?
newHead = 5。 -
調整指針：
3.next.next = 3?→?4.next = 3（形成?5 → 4 → 3）。 -
斷開原鏈：
3.next = null。
-
-
輸出鏈表狀態：
5 → 4 → 3 → null -
返回：
newHead = 5
層 2（head = 2）
-
輸入鏈表狀態：
2 → 3 → null（原鏈未修改時，2.next?指向?3）。 -
操作步驟：
-
收到下層返回的?
newHead = 5。 -
調整指針：
2.next.next = 2?→?3.next = 2（形成?5 → 4 → 3 → 2）。 -
斷開原鏈：
2.next = null。
-
-
輸出鏈表狀態：
5 → 4 → 3 → 2 → null -
返回：
newHead = 5
層 1（head = 1）
-
輸入鏈表狀態：
1 → 2 → null（原鏈未修改時，1.next?指向?2）。 -
操作步驟：
-
收到下層返回的?
newHead = 5。 -
調整指針：
1.next.next = 1?→?2.next = 1（形成?5 → 4 → 3 → 2 → 1）。 -
斷開原鏈：
1.next = null。
-
-
輸出鏈表狀態：
5 → 4 → 3 → 2 → 1 → null -
返回：
newHead = 5
總結
-
遞歸終止條件：處理到鏈表末尾時直接返回。
-
遞歸分解問題：假設后續鏈表已反轉，只需調整當前節點和下一個節點的指針。
-
指針操作：通過?
head.next.next = head?和?head.next = null?完成局部反轉并斷開原鏈。
)
)
