前言
上篇文章已經從底層完整實現了一個單鏈表這樣的數據結構，並且也依託鏈表這樣的數據結構實現了棧和隊列，在實現隊列的時候對鏈表進行了一些改進。
遞歸不光用於樹這樣的結構中還可以用在鏈表這樣的結構中，鏈表本身就天然的具有遞歸結構性質，只不過鏈表太簡單了，它是一個線性結構，所以可以使用非遞歸的方式，如使用循環的方式就可以非常容易的解決鏈表的問題，從鏈表開始就要打好遞歸的基礎，對深入學習樹結構包括更加深刻的理解遞歸算法都是非常有好處的。
還是那句老話：光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。源碼倉庫
不要完美主義。掌握好“度”。
太過於追求完美會把自己逼的太緊，會產生各種焦慮的心態，最後甚至會懷疑自己，溫故而知新，不要停止不前，掌握好這個度，不存在你把那些你認為完全掌握了，然後就成了某一個領域的專家，相反一旦你產生很濃厚的厭惡感，那麼就意味著你即將會放棄或者已經選擇了放棄，雖然你之前想把它做到 100 分，但是由於你的放棄讓它變為 0 分。
學習本著自己的目標去。不要在學的過程中偏離了自己的目標。要分清主次。
難的東西，你可以慢慢的回頭看一看。那樣才會更加的柳暗花明，更能提升自己的收穫。
鏈表與遞歸
通過 leetcode 上與鏈表相關的問題來學習遞歸，在 leetcode 上提交鏈表相關的問題，還有一些其它需要注意的地方，與此同時在 leetcode 上解決與鏈表相關的問題，思路在有一些地方和之前自自定義鏈表是不同的，這裡面的關鍵不同是在於有些情況下做這些程序是以節點為中心的而不會包裝一個整體的鏈表類。
leectcode 203 號問題：刪除鏈表中的元素
先找到這個鏈表中這個節點之前的那個節點，但是對於頭節點來說沒有之前的那個節點，所以就要特殊處理或者使用虛擬頭節點來統一這個操作。
為了更好的測試，我自定義了一個將數組轉換為鏈表的方法。
方法解析：鏈表的第一個節點就是你創建的這個節點，這個節點的值也是數組的第一個值，其它的節點通過第一個節點的 next 進行關聯，對應的值為數組中的每個值。
代碼及測試用例
(class: ListNode, class: Solution,class: Solution2, class: Main)
ListNode
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
// 將一個數組對象 轉換為一個鏈表 並且追加到當前節點上
appendToLinkedListNode(array) {
let head = null;
if (this.val === null) {
// 頭部添加
head = this;
head.val = array[0];
head.next = null;
} else {
// 插入式
head = new ListNode(array[0]);
head.next = this.next;
this.next = head;
}
// 添加節點的方式 頭部添加、尾部添加、中間插入
// 尾部添加節點的方式
for (var i = 1; i < array.length; i++) {
head.next = new ListNode(array[i]);
head = head.next;
}
}
// 輸出鏈表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `ListNode: \n`;
arrInfo += `data = front [`;
let node = this;
while (node.next !== null) {
arrInfo += `${node.val}->`;
node = node.next;
}
arrInfo += `${node.val}->`;
arrInfo += 'NULL] tail';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Solution
class Solution {
// leetcode 203. 移除鏈表元素
removeElements(head, val) {
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
// 對頭步進行特殊處理
while (head !== null && head.val === val) {
head = head.next;
}
// 處理後的頭部如果為null 那直接返回
if (head === null) {
return null;
}
// 因為頭部已經做了特殊處理， head即不為null 並且 head.val不等於null
// 那麼可以直接從 head的下一個節點開始判斷。
let prev = head;
while (prev.next !== null) {
if (prev.next.val === val) {
let delNode = prev.next;
prev.next = delNode.next;
delNode = null;
} else {
prev = prev.next;
}
}
return head;
};
}Solution2
class Solution {
// leetcode 203. 移除鏈表元素
removeElements(head, val) {
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
if (head === null) {
return null;
}
let dummyHead = new ListNode(0);
dummyHead.next = head;
let cur = dummyHead;
while (cur.next !== null) {
if (cur.next.val === val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummyHead.next;
};
return removeElements(head, val);
}
}Main
class Main {
constructor() {
this.alterLine('leetcode 203. 刪除指定元素的所有節點');
let s = new Solution();
let arr = [1, 2, 3, 5, 1, 2, 1, 3, 5, 3, 5, 6, 3, 1, 5, 1, 3];
let node = new ListNode(null);
node.appendToLinkedListNode(arr);
console.log(node.toString());
let result = s.removeElements(node, 1);
console.log(result.toString());
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};遞歸
遞歸是極其重要的一種組建邏輯的機制，尤其是在計算機的世界中對於高級的排序算法通常都需要使用遞歸，對於計算機科學來說熟練的掌握遞歸是極其重要的，甚至可以說初級水平與高級水平之間差距的關鍵分水嶺。
遞歸可以做分形圖形的繪製，各種高級排序算法的可視化。
遞歸的本質就是將原來的問題，轉化為更小的同樣的一個問題，也就是將問題規模逐漸縮小，小到一定程度，通常在遞歸中都是小到不能再小的時候就可以很容易的解決問題，這樣一來整個問題就可以得到解決。
使用遞歸的例子
數組求和：求數組中 n 個元素的和
Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1]) 第一次， Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1]) 第二次， ... 若干次 Sum(arr[n-1...n-1]) = arr[n-1] + Sum(arr[]) 最後一次。
每一次都是將同一個問題慢慢更小化從而演化成最基本的問題，最基本的問題解決了，然後根據之前的一些邏輯，從而解決原問題，就像一個大問題，如果他可以分解成無數個性質相同的小問題，然後對這些小問題以遞歸的形式進行處理，這樣一來就容易多了。
代碼中if (arr.length == cur) {return 0;}就是解決最基本的問題，代碼中arr[cur] + sum(arr, cur+1);就是在構建原問題的答案。
代碼中sum(arr, cur+1);就是不斷的將原問題轉化為更小的問題，很多個小問題的解加到一起，就構建出原問題的答案了。
class Calc {
constructor() {}
// 遞歸求和
sum(array, cur = 0) {
// 解決最基本的問題
if (cur === array.length) {
return 0;
}
// 化歸思想
// 將原問題分解為性質相同的小問題
// 將眾多小問題的答案構建出原問題的答案
return array[cur] + this.sum(array, cur + 1);
}
// 尾遞歸求和
tailSum(array, cur = 0, result = 0) {
// 解決最基本的問題
if (cur === array.length) {
return result; // 這裡是上面的sum不一樣，這裡直接返回最終計算結果
}
// 化歸思想 ： 將原問題分解為性質相同的小問題，使用小問題的解構建出原問題的解。
// 減少或者複用程序調用系統棧： 將運算操作一次性執行完畢，然後再執行子函數。
return this.tailSum(array, cur + 1, result + array[cur]);
}
}
class Main {
constructor() {
this.alterLine('遞歸求和');
let calc = new Calc();
let arr = [1, 2, 3, 4];
let arrInfo = `[`;
for (var i = 0; i < arr.length - 1; i++) {
arrInfo += `${arr[i]},`;
}
arrInfo += `${arr[arr.length - 1]}`;
arrInfo += `]`;
document.body.innerHTML += `${arrInfo}<br /><br />`;
this.show(calc.sum(arr));
this.show(calc.tailSum(arr));
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};小結
對於一個複雜的遞歸算法來說，這個邏輯可能是非常複雜的，雖然說轉化問題是一個難點，實際上也並不是那麼難，只不過很多在寫邏輯的時候把自己給繞暈了，函數自己調用自己，不必過於糾結這裡面程序執行的機制。
寫遞歸函數的時候一定要注重遞歸函數本身的語意，例如上面的 sum 函數，它就是用來計算一個數組從索引 cur 開始到最後一個位置之間所有的數字之和，這個就是此遞歸函數的“宏觀”語意，在這樣的一個語意下，在涉及轉換邏輯的時候你要拋棄掉這是一個遞歸算法的這樣的想法，遞歸函數本身它也是一個函數，每個函數其實就是完成一個功能。
在函數 A 中調函數 B 你並不會暈，但是在函數 A 裡調用函數 A，也就是在遞歸函數中你可能就會暈，其實這和函數 A 裡調用函數 B 在本質上並沒有區別。
你可以當這是一個子邏輯，這個子邏輯裡面需要傳兩個參數，它做的事情就是求數組裡的從索引 cur 開始到最後一個位置之間所有的數字之和，你就僅僅是在用這個函數，至於或者函數是不是當前函數沒必要在意，其實就是這麼簡單的一件事情。
在寫遞歸算法的時候，有些時候不需要你特別微觀的陷進遞歸調用裡的去糾結這個遞歸是怎麼樣調用的，其實你可以直接把這個遞歸函數當成一個子函數，這個子函數可以完成特定的功能，而你要乾的事情就是利用這個子函數來構建你自己的邏輯，來解決上層的這一個問題就好了。
注意遞歸函數的宏觀語意把你要調用的遞歸函數當作是一個子函數或者子邏輯或者子過程，然後去想這個子過程如果去幫你解決現在的這個問題就 ok，要想熟練的掌握就需要大量的練習。
鏈表的天然遞歸結構性質，解答 leectcode 203 號問題
class Solution {
// leetcode 203. 移除鏈表元素
removeElements(head, val) {
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
// 遞歸求解三種方式
var removeElements = function(head, val) {
// 解決最基本的問題
if (head === null) {
return null;
}
// 第一種解決方式
// let node = removeElements(head.next, val);
// if (head.val === val) {
// head = node;
// } else {
// head.next = node;
// }
// return head;
// 第二種解決方式
// if (head.val === val) {
// head = removeElements(head.next, val);
// } else {
// head.next = removeElements(head.next, val);
// }
// return head;
// 第三種方式
head.next = removeElements(head.next, val);
if (head.val === val) {
return head.next;
} else {
return head;
}
};
// 尾遞歸的方式 失敗 沒有到達那個程度
// var removeElements = function(head, val, node = null) {
// if (head === null) {
// return node;
// }
// return removeElements(head.next, val , node = head);
// }
return removeElements(head, val);
}
}
class Main {
constructor() {
this.alterLine('leetcode 203. 刪除指定元素的所有節點(遞歸)');
let s = new Solution();
let arr = [1, 2, 3, 5, 1, 2, 1, 3, 5, 3, 5, 6, 3, 1, 5, 1, 3];
let node = new ListNode(null);
node.appendToLinkedListNode(arr);
console.log(node.toString());
let result = s.removeElements(node, 2);
console.log(result.toString());
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};遞歸運行的機制及遞歸的“微觀”解讀
雖然寫遞歸函數與遞歸算法時要注意遞歸算法的宏觀語意，但是站在一個更高的層面去思考這個函數它本身的功能作用是什麼，也許可以幫助你更好的完成整個遞歸的邏輯，但是從另外一方面遞歸函數想，遞歸函數到底是怎樣運轉的，它內部的機制是怎樣的，所以遞歸的運行機制也是需要了解的。
通過數組求和與刪除鏈表節點的遞歸實現來具體的觀察遞歸的運行機制，棧的應用中說過程序調用的系統棧，子函數調用的位置會壓入到一個系統棧，當子函數調用完成的時候，程序就會從系統棧中找到上次父函數調用子函數的這個位置，然後再父函數中的子函數這個位置後續繼續執行，其實遞歸調用和子函數子過程的調用沒有區別，只不過遞歸調用的函數還是這個函數本身而已(自己調用自己，根據某些條件終止調用自己)。
遞歸的調用和子過程的調用是沒有區別的，就像程序調用的系統棧一樣。
父函數調用子函數，子函數執行完畢之後，就會返回到上一層，也就是繼續執行父函數，這個執行並不是重新執行，而是從之前那個子函數調用時的位置繼續往下執行，如果子函數有返回值，那麼接收一下也可以，接收完了之後繼續往下執行。
A0();
function A0 () {
...
A1();
...
}
function A1 () {
...
A2();
...
}
function A2 () {
...
...
...
}遞歸的調用時有代價的
是函數調用 + 系統棧空間。比如系統棧中會記錄這些函數調用的信息，如當前這個函數執行到哪兒了，當前的局部變量都是怎樣的一個狀態，然後給它壓入系統棧。
包括函數調用的本身在計算機的底層找到這個新的函數所在的位置，這些都是有一定的時間消耗的。
遞歸調用的過程是很消耗系統棧的空間的，如果遞歸函數中沒有處理那個最基本的情況，那麼遞歸將一直執行下去，不會正常終止，最終終止的結果肯定就是異常報錯，因為系統棧佔滿了，空間不足。
在線性的調用過程中，當你遞歸的次數達到十萬百萬級別的話，系統佔還是會被佔滿，因為存儲了太多函數調用的狀態信息。
用遞歸書寫邏輯其實是更簡單的，這一點在線性的結構中看不出來，這是因為線性的結構非常好想，直接寫循環就能解決所有的線性問題，但是一旦進入非線性的結構 如樹、圖，很多問題其實使用遞歸的方式解決將更加的簡單。
數組求和的遞歸解析
原函數
// 計算 arr[cur...n] 這個區間內的所有數字之和。
sum (arr, cur = 0) {
// 這個地方就是求解最基本問題
// 通常對於遞歸算法來說，
// 最基本的問題就是極其簡單的，
// 基本上都是這樣的一種形式
// 因為最基本的問題太過於平凡了
// 一眼就看出來那個答案是多少了
if (arr.length === cur) {
return 0;
}
// 這部分就是遞歸算法f最核心的部分
// 把原問題轉化成更小的問題的一個過程
// 這個過程是難的，
// 這個轉化為更小的問題並不簡單的求一個更小的問題的答案就好了，
// 而是要根據這個更小的問題的答案構建出原問題的答案，
// 這個構建 在這裡就是一個加法的過程。
return arr[cur] + this.sum(arr, cur + 1);
}解析原函數
遞歸函數的調用，本質就是就是函數調用，只不過調用的函數就是自己而已。
// 計算 arr[cur...n] 這個區間內的所有數字之和。
sum (arr, cur = 0) {
if (arr.length === cur) {
return 0;
}
temp = sum(arr, cur + 1);
result = arr[cur] + temp;
return result;
}在 sum 函數中調用到了 sum 函數，實際上是在一個新的 sum 函數中 調用邏輯，原來的 sum 函數中所有的變量保持不變，等新的 sum 函數執行完了邏輯，還會回到原來的 sum 函數中繼續執行餘下的邏輯。
// 計算 arr[cur...n] 這個區間內的所有數字之和。
// 代號 001
// 使用 arr = [6, 10]
// 調用 sum(arr, 0)
sum (arr, cur = 0) {
if (cur == n) return 0; // n 為數組的長度：2
temp = sum(arr, cur + 1); // cur 為 0
result = arr[cur] + temp;
return result;
}
// 代號 002
// 到了 上面的sum(arr, cur + 1)時
// 實際 調用了 sum(arr, 1)
sum (arr, cur = 0) {
if (cur == n) return 0; // n 為數組的長度：2
temp = sum(arr, cur + 1); // cur 為 1
result = arr[cur] + temp;
return result;
}
// 代號 003
// 到了 上面的sum(arr, cur + 1)時
// 實際 調用了 sum(arr, 2)
sum (arr, cur = 0) {
// n 為數組的長度：2，cur 也為：2
// 所以sum函數到這裡就終止了
if (cur == n) return 0;
temp = sum(arr, cur + 1); // cur 為 2
result = arr[cur] + temp;
return result;
}
// 上面的代號003的sum函數執行完畢後 返回 0。
//
// 那麼 上面的代號002的sum函數中
// temp = sum(arr, cur + 1)，temp獲取到的值 就為 0，
// 然後繼續執行代號002的sum函數裡temp獲取值時中斷的位置 下面的邏輯，
// 執行到了result = arr[cur] + temp，
// temp為 0，cur 為 1，arr[1] 為 10，所以result 為 0 + 10 = 10，
// 這樣一來 代號002的sum函數執行完畢了，返回 10。
//
// 那麼 代號001的sum函數中
// temp = sum(arr, cur + 1)，temp獲取到的值 就為 10，
// 然後繼續執行代號001的sum函數裡temp獲取值時中斷的位置 下面的邏輯，
// 執行到了result = arr[cur] + temp，
// temp為 10，cur 為 0，arr[0] 為 6，所以result 為 6 + 10 = 16，
// 這樣一來 代號001的sum函數執行完畢了，返回 16。
//
// 代號001的sum函數沒有被其它代號00x的sum函數調用，
// 所以數組求和的最終結果就是 16。調試遞歸函數的思路
如果對遞歸函數運轉的機制不理解，不要對著遞歸函數去生看生想，在很多時候你肯定會越想越亂，不如你用一個非常小的測試數據集直接扔進這個函數中，你可以使用紙筆畫或者使用 瀏覽器 提供的 debug功能，一步一步的去看這個程序在每一步執行後計算的結果是什麼。
通常使用這種方式能夠幫助你更加清晰的理解程序的運轉邏輯，計算機是一門工科，和工程相關的科學，工程相關的科學雖然也注重理論它背後也有理論支撐，但是從工程的角度入手來實踐是非常非常重要的。
很多時候你如果想理解它背後的理論，可能更好的方式不是去想這個理論，而是實際的去實踐一下看看這個過程到底是怎麼回事兒。
刪除鏈表節點的遞歸解析
原函數
var removeElements = function(head, val) {
if (head == null) {
return null;
}
head.next = removeElements(head.next, val);
if (head.val == val) {
return head.next;
} else {
return head;
}
};解析原函數
遞歸調用的時候就是子過程的調用，一步一步的向下調用，調用完畢之後，子過程計算出結果後再一步一步的返回給上層的調用，最終得到了最終的結果，6->7->8->null 刪除掉 7 之後就是 6->8->null，節點真正的刪除是發生在步驟 3 中，在使用解決了一個更小規模的問題相應的解之後，結合當前的調用，組織邏輯，組織出了當前這個問題的解，就是這樣的一個過程。
// 操作函數編號 001
var removeElements = function(head, val) {
// head：6->7->8->null
//步驟1
if (head == null) return null;
//步驟2
head.next = removeElements(head.next, val);
//步驟3
return head.val == val ? head.next : head;
};
// 模擬調用，對 6->7->8->null 進行7的刪除
// 調用 removeElments(head, 7);
// 執行步驟1，head當前的節點為6，既然不為null，所以不返回null，
// 繼續執行步驟2，head.next = removeElements(head.next, 7)，
// 求當前節點後面的一個節點，後面的一個節點目前不知道，
// 但是可以通過removeElements(head.next, 7)這樣的子過程調用求出來，
// 這次傳入的是當前節點的next，也就是7的這個節點，7->8->null。
// 操作函數編號 002
var removeElements = function(head, val) {
// head：7->8->null
//步驟1
if (head == null) return null;
//步驟2
head.next = removeElements(head.next, val);
//步驟3
return head.val == val ? head.next : head;
};
// 模擬調用，對 7->8->null 進行7的刪除
// 調用 removeElements(head.next, 7);
// head.next 會被賦值給 函數中的局部變量 head，
// 也就是調用時被轉換為 removeElements(head, 7);
// 執行步驟1，head當前的節點為7，不為null，所以也不會返回null，
// 繼續執行步驟2，head.next = removeElements(head.next, 7)，
// 求當前節點後面的一個節點，後面的一個節點目前不知道，
// 但是可以通過removeElements(head.next, 7)這樣的子過程調用求出來，
// 這次傳入的也是當前節點的next，也就是8的這個節點，8->null。
// 操作函數編號 003
var removeElements = function(head, val) {
// head：8->null
// 步驟1
if (head == null) return null;
// 步驟2
head.next = removeElements(head.next, val);
// 步驟3
return head.val == val ? head.next : head;
};
// 模擬調用，對 8->null 進行7的刪除
// 調用 removeElements(head.next, 7);
// head.next 會被賦值給 函數中的局部變量 head，
// 也就是調用時被轉換為 removeElements(head, 7);
// 執行步驟1，head當前的節點為7，不為null，所以也不會返回null，
// 繼續執行步驟2，head.next = removeElements(head.next, 7)，
// 求當前節點後面的一個節點，後面的一個節點目前不知道，
// 但是可以通過removeElements(head.next, 7)這樣的子過程調用求出來，
// 這次傳入的也是當前節點的next，也就是null的這個節點，null。
// 操作函數編號 004
var removeElements = function(head, val) {
// head：null
// 步驟1
if (head == null) return null;
// 步驟2
head.next = removeElements(head.next, val);
// 步驟3
return head.val == val ? head.next : head;
};
// 模擬調用，對 null 進行7的刪除
// 調用 removeElements(head.next, 7);
// head.next 會被賦值給 函數中的局部變量 head，
// 也就是調用時被轉換為 removeElements(head, 7);
// 執行步驟1，head當前的節點為null，直接返回null，不繼續向下執行了。
// 操作函數編號 003
var removeElements = function(head, val) {
// head：8->null
//步驟1
if (head == null) return null;
//步驟2
head.next = removeElements(head.next, val);
//步驟3
return head.val == val ? head.next : head;
};
// 這時候回到操作函數編號 004的上一層中來，
// 操作函數編號 003 調用到了步驟2，並且head.next接收到的返回值為null,
// 繼續操作函數編號 003 的步驟3，判斷當前節點的val是否為7，
// 很明顯函數編號003裡的當前節點的val為8，所以返回當前的節點 8->null。
// 操作函數編號 002
var removeElements = function(head, val) {
// head：7->8->null
//步驟1
if (head == null) return null;
//步驟2
head.next = removeElements(head.next, val);
//步驟3
return head.val == val ? head.next : head;
};
// 這時候回到操作函數編號 003的上一層中來，
// 操作函數編號 002 調用到了步驟2，head.next接收到的返回值為節點 8->null，
// 繼續操作函數編號 002 的步驟3，判斷當前節點的val是否為7，
// 此時函數編號 002 的當前節點的val為7，所以返回就是當前節點的next 8->null，
// 也就是說不返回當前的節點 head：7->8->null ，改返回當前節點的下一個節點，
// 這樣一來就相當於刪除了當前這個節點，改讓父節點的next指向當前節點的next。
// 操作函數編號 001
var removeElements = function(head, val) {
// head：6->7->8->null
//步驟1
if (head == null) return null;
//步驟2
head.next = removeElements(head.next, val);
//步驟3
return head.val == val ? head.next : head;
};
// 這時候回到操作函數編號 002的上一層中來，
// 操作函數編號 001 調用到了步驟2，head.next接收到的返回值為節點 8->null，
// 繼續操作函數編號 001 的步驟3，判斷當前節點的val是否為7，
// 函數編號 001 中當前節點的val為6，所以返回當前的節點 head：6->8->null，
// 之前當前節點 為head：6->7->8->null，由於head.next在步驟2時發生了改變，
// 原來老的head.next（head：7->8->null） 從鏈表中剔除了，
// 所以當前節點 為head：6->8->null。
// 鏈表中包含節點的val為7的節點都被剔除，操作完畢。遞歸算法的調試
可以以動畫的方式展示遞歸函數底層的運行機理，一幀一幀的動畫來展示遞歸函數的具體執行過程。
但是在實際調試遞歸函數時
- 很難畫出那麼詳細的動畫，相對也比較費時間，
- 但是也可以拿一張 A4 的白紙仔細的一下，
- 例如 畫一個比較小的測試用例的執行過程是怎樣的，
- 這樣對於理解你的程序或者找出你的程序中有錯誤，
- 是非常有幫助的
調試方法靠打印輸出，完全可以使用打印輸出的方式清楚的看出程序在執行過程中是怎樣一步一步獲得最終結果。單步跟蹤，也就是每一個 IDE 中自帶的調試功能。視情況來定。
對於遞歸函數來說有一個非常重要的概念，遞歸的深度，每一個函數在自己的內部都會去調用了一下自己，那麼就代表每次調用自己時，整個遞歸的深度就多了 1，所以在具體的輸出可視化這個遞歸函數時，這個遞歸深度是可以幫助你理解這個遞歸過程的一個變量，在原遞歸函數中新增一個參數depth，根據這個變量生成遞歸深度字符串--，--相同則代表同一遞歸深度。
很多時候要想真正理解一個算法或者理解一個函數，其實並沒有什麼捷徑，肯定是要費一些勁，如果你不想在紙上畫出來的話，那麼你就要用代碼畫出來，也就是要在代碼上添加很多的輔助代碼，這就是平時去理解程序或做練習時不要去犯懶，可能只要寫 4 行代碼就能解決問題，但是這背後很有可能是你寫了幾十行甚至上百行的代碼最終終於透徹的理解了這個程序，然後才能瀟灑的用四行代碼來解決這個問題。
不停的練習如何寫一個遞歸的函數，才能理解理解這個遞歸的過程。
代碼示例
(class: ListNode, class: Solution)
ListNode
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
// 將一個數組對象 轉換為一個鏈表 並且追加到當前節點上
appendToLinkedListNode(array) {
let head = null;
if (this.val === null) {
// 頭部添加
head = this;
head.val = array[0];
head.next = null;
} else {
// 插入式
head = new ListNode(array[0]);
head.next = this.next;
this.next = head;
}
// 添加節點的方式 頭部添加、尾部添加、中間插入
// 尾部添加節點的方式
for (var i = 1; i < array.length; i++) {
head.next = new ListNode(array[i]);
head = head.next;
}
}
// 輸出鏈表中的信息
// @Override toString 2018-10-21-jwl
// toString () {
// let arrInfo = `ListNode: \n`;
// arrInfo += `data = front [`;
// let node = this;
// while (node.next !== null) {
// arrInfo += `${node.val}->`;
// node = node.next;
// }
// arrInfo += `${node.val}->`;
// arrInfo += "NULL] tail";
// // 在頁面上展示
// document.body.innerHTML += `${arrInfo}<br /><br /> `;
// return arrInfo;
// }
toString() {
let arrInfo = `ListNode = `;
arrInfo += `front [`;
let node = this;
while (node.next !== null) {
arrInfo += `${node.val}->`;
node = node.next;
}
arrInfo += `${node.val}->`;
arrInfo += 'NULL] tail';
return arrInfo;
}
}Solution
class Solution {
// leetcode 203. 移除鏈表元素
removeElements(head, val) {
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
// 深入理解遞歸過程
var removeElements = function(head, val, depth = 0) {
// 首次輸出 開始調用函數
let depthString = generateDepathString(depth);
let info = depthString + 'Call: remove ' + val + ' in ' + head;
show(info);
if (head === null) {
// 第二次輸出 解決最基本的問題時
info = depthString + 'Return ：' + head;
show(info);
return null;
}
let result = removeElements(head.next, val, depth + 1);
// 第三次輸出 將原問題分解為小問題
info = depthString + 'After： remove ' + val + ' ：' + result;
show(info);
let ret = null;
if (head.val === val) {
ret = result;
} else {
head.next = result;
ret = head;
}
// 第四次輸出 求出小問題的解
info = depthString + 'Return ：' + ret;
show(info);
return ret;
};
// 輔助函數 生成遞歸深度字符串
function generateDepathString(depth) {
let arrInfo = ``;
for (var i = 0; i < depth; i++) {
arrInfo += `-- `; // -- 表示深度，--相同則代表在同一遞歸深度
}
return arrInfo;
}
// 輔助函數 輸出內容 到頁面和控制檯上
function show(content) {
document.body.innerHTML += `${content}<br /><br />`;
console.log(content);
}
return removeElements(head, val);
}
}
class Main {
constructor() {
this.alterLine('leetcode 203. 刪除指定元素的所有節點(遞歸) 調試');
let s = new Solution();
let arr = [1, 2, 3];
let node = new ListNode(null);
node.appendToLinkedListNode(arr);
this.show(node);
s.removeElements(node, 2);
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}總結
關於遞歸，鏈表有天然遞歸性質結構，幾乎和鏈表相關的所有操作，都可以使用遞歸的形式完成。
練習時可以對鏈表的增刪改查進行遞歸實現，之前鏈表的增刪改查使用了循環的方式進行了實現，現在可以對鏈表的增刪改成進行遞歸的方式實現，這個練習是非常有意義的，能夠幫助你更好的理解遞歸。雖然實際使用鏈表時是不需要使用遞歸的，但是進行一下這種練習可以讓你更好的對遞歸有更深刻的理解。
其它和鏈表相關的題目 leetcode 上有，鏈表：https://leetcode-cn.com/tag/linked-list/。
不要完美主義，不要想著把這些問題一下子全部做出來，根據自己的實際情況來制定計劃，在自己處於什麼樣的水平的時候，完成怎樣的問題，但是這些問題一直都會在 leetcode 上，慢慢來，一點一點的實現。
關於鏈表的技術研究，由斯坦福提出的問題研究，文章地址：https://max.book118.com/html/2017/0902/131359982.shtm，都看懂了，那你就完全的懂了鏈表。
非線性數據結構，如大名鼎鼎的二分搜索樹二分搜索樹也是一個動態的數據結構也是靠節點掛接起來的，只不過那些節點沒有排成一根線，而是排成了一顆樹，不是每一個節點有指向下一個節點的 next，而是由指向左子樹和右子樹的兩個根節點而已。
擴展
雙鏈表
對於隊列來說需要對鏈表的兩端進行操作，在兩端進行操作的時候就遇到了問題，在尾端刪除元素，即使在尾端有 tail 的變量指向鏈表的結尾，它依然是一個O(n)複雜度的。
對於這個問題其實有一個解決方案，這個問題的解決方案就是雙鏈表，所謂的雙鏈表就是在鏈表中每一個節點包含兩個指針指針就代表著引用，有一個變量 next 指向這個節點的下一個節點，有一個變量 prev 指向這個節點的前一個節點，對於雙鏈表來說，你有了 tail 這個節點之後，刪除尾部的節點就非常簡單，而且這個操作會是O(1)級別的，但是代價是每一個節點從原來只有一個指針變為兩個指針，那麼維護起來就會相對複雜一些。
class Node {
e; // Element
next; //Node
prev; //Node
}循環鏈表
對於循環鏈表來說，也可以使用雙鏈表的思路來實現，不過需要設立一個虛擬的頭節點，從而讓整個鏈表形成了一個環，這裡面最重要的是 尾節點不指向空而是指向虛擬頭節點，可以很方便的判斷某一個節點的下一個節點是否是虛擬頭節點，來確定這個節點是不是尾節點。
循環鏈表的好處是 進一步的把很多操作進行了統一。比如說在鏈表結尾添加元素只需要在 dummyHead 的前面添加要一個給元素，它就等於是在整個鏈表的結尾添加了一個元素，事實上循環鏈表本身是非常有用的，是強類型語言 Java 中的 LinkedList 類底層的實現，本質就是一個循環鏈表，更準確一些，就是循環雙向鏈表，因為每個節點是有兩個指針的。
鏈表也是使用數組來實現
因為鏈表的 next 只是指向下一個元素，在數組中每一個位置存儲的不僅僅是有這個元素，再多存儲一個指向下一個元素的索引。
這個鏈表中每一個節點是這樣的，Node 類中有一個 int 的變量 next 指向下一個元素的索引。在有一些情況下，比如你明確的知道你要處理的元素有多少個，這種時候使用這種數組鏈表有可能是更加方便的。
class Node {
e; // Element
next; //int
}