---

theme: fancy highlight: a11y-dark

---

嗨！~ 大家好，我是YK菌 🐷 ，一個微系前端 ✨，喜歡分享自己學到的小知識 🏹，歡迎關注我呀 😘 ~ [微訊號: yk2012yk2012，微信公眾號：ykyk2012]

「這是我參與11月更文挑戰的第6天，活動詳情檢視：2021最後一次更文挑戰」

今天來一道特別經典也是特別高頻的題，反轉連結串列。我們分別使用遞迴與非遞迴的方式來解決這道題，但是這裡遞迴的方式比較難理解，需要好好思考，可以幫助我們剛好的瞭解遞迴的思想

206. 反轉連結串列

給你單鏈表的頭節點 head ，請你反轉連結串列，並返回反轉後的連結串列。

【解法一】非遞迴

這裡是反轉連結串列不是反轉陣列，所以我們直接修改結點之間的指標就可以實現反轉連結串列的操作了！

舉一個連結串列的例子：3 -> 2 -> 1 ，我們先反轉前兩個結點的指標關係，得到 3 <- 2 -> 1 ， 此時我們再反轉後面的指標得到 3 <- 2 <- 1 此時我們就將連結串列反轉了，順序遍歷的話就是 1 -> 2 -> 3

1. 初始化

js let prev = null; let curr = head;

那我們現就只需要聚焦在如何改變兩個結點之間的指標即可

1. 指標反轉

js let temp = curr.next; curr.next = prev;

1. 後移指標 js prev = curr; curr = temp;

2. 一次的結果

迴圈遍歷反轉所有指標即可

javascript var reverseList = function(head) { let prev = null; let curr = head; while (curr) { let temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; };

用一個動圖演示就是這樣 動圖連結

最後來看看結果

【解法二】遞迴

我們這樣思考，一個連結串列，如果在某個位置，後面部分都已經反轉了，那它前面部分怎麼操作

採用遞迴的方式來解題，從頭結點開始遞迴到底，遞迴出口就是最後一個結點。最後一個節點作為反轉後的頭節點。

然後就是在每一層遞迴種進行反轉的操作，動圖如下

動圖連結

```javascript var reverseList = function(head) { // 遞迴出口，返回最後一個節點作為反轉後的頭結點 if (head == null || head.next == null) { return head; }

// 新頭結點newHead指向尾結點，此處進入遞迴，遞迴一直到遍歷到尾結點時才會返回
const newHead = reverseList(head.next);

// 每一層遞迴操作，讓head的下一個節點指向自己【反轉】
head.next.next = head;
// head指向null。以此達到反轉的目的。
head.next = null;

return newHead;

}; ```

最後，歡迎關注我的專欄，和YK菌做好朋友~