你不會永遠順?biāo)?#xff0c;更不會一直年輕，你太安靜了，是時候出發(fā)了

????????????????????????????????????????????????????????????????????????????????????????——?24.12.2

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 = []
輸出：[]

方法一 雙指針迭代

定義兩個指針pre、temp，pre指針指向null，然后將給出的鏈表從頭節(jié)點head進行遍歷，先將temp指針指向head.next節(jié)點，將遇到的節(jié)點head的next指向置為pre指針：head.next = pre，（pre指針指向空值，第一次迭代則將原鏈表最后一個元素作為翻轉(zhuǎn)后的鏈表的第一個元素），然后再將head指針的指向修改回先前存儲的temp指針處，將整個原鏈表遍歷完成，則對鏈表翻轉(zhuǎn)完成

---

Java實現(xiàn)

/*** 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 pre = null;while(head != null) {ListNode tmp = head.next; // 暫存后繼節(jié)點 head.nexthead.next = pre;          // 修改 next 引用指向pre = head;               // pre 暫存 headhead = tmp;               // head 訪問下一節(jié)點}return pre;}
}

---

Python實現(xiàn)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:cur, pre = head, Nonewhile head:# 1.將頭結(jié)點的下一個節(jié)點暫存在temp中temp = cur.next# 2.頭結(jié)點的下一個節(jié)點存入pre指針中cur.next = pre# 3.pre指針指向頭結(jié)點，即pre指針永遠指向新鏈表添加節(jié)點的位置，而新節(jié)點一直隨著頭結(jié)點更新而更新pre = cur# 4.將頭結(jié)點指向一開始存入的下一個節(jié)點，起到遍歷的作用cur = temp# 返回構(gòu)造的翻轉(zhuǎn)后的新鏈表return pre

---

方法二 遞歸

考慮使用遞歸法遍歷鏈表，當(dāng)越過尾節(jié)點后終止遞歸，在回溯時修改各節(jié)點的next引用指向。

遞歸函數(shù):recur(cur,pre)

1.終止條件:當(dāng) cur 為空，則返回尾節(jié)點pre(即反轉(zhuǎn)鏈表的頭節(jié)點)

2.遞歸后繼節(jié)點，記錄返回值(即反轉(zhuǎn)鏈表的頭節(jié)點)，為res

3.修改當(dāng)前節(jié)點 cur 引用指向前驅(qū)節(jié)點 pre;

4.返回反轉(zhuǎn)鏈表的頭節(jié)點 res

reverseList(head)函數(shù)：

調(diào)用并返回recur(head，null)。

傳入null是因為反轉(zhuǎn)鏈表后，head節(jié)點指向 null;

---

Java實現(xiàn)

/*** 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) {return recur(head, null);    // 調(diào)用遞歸并返回}private ListNode recur(ListNode cur, ListNode pre) {if (cur == null){return pre; // 終止條件}ListNode res = recur(cur.next, cur);  // 遞歸后繼節(jié)點cur.next = pre;              // 修改節(jié)點引用指向return res;                  // 返回反轉(zhuǎn)鏈表的頭節(jié)點}
}

---

Python實現(xiàn)?

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: ListNode) -> ListNode:def recur(cur, pre):if not cur: return pre     # 終止條件res = recur(cur.next, cur) # 遞歸后繼節(jié)點cur.next = pre             # 修改節(jié)點引用指向return res                 # 返回反轉(zhuǎn)鏈表的頭節(jié)點return recur(head, None)       # 調(diào)用遞歸并返回