摘要：鏈表與遞歸已經從底層完整實現了一個單鏈表這樣的數據結構，并且也依托鏈表這樣的數據結構實現了棧和隊列，在實現隊列的時候對鏈表進行了一些改進。計算這個區間內的所有數字之和。

【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文章大概的內容如下：
Arrays(數組)、Stacks(棧)、Queues(隊列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優先隊列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(并查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(哈希表)

源代碼有三個：ES6（單個單個的 class 類型的 js 文件） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)

全部源代碼已上傳 github，點擊我吧，光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。

本文章適合 對數據結構想了解并且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時間跨度也算將近半年時間了，希望對想學習數據結構的人或者正在學習數據結構的人群有幫助。

已經從底層完整實現了一個單鏈表這樣的數據結構，

并且也依托鏈表這樣的數據結構實現了棧和隊列，

在實現隊列的時候對鏈表進行了一些改進。

遞歸不光用于樹這樣的結構中還可以用在鏈表這樣的結構中

鏈表本身就天然的具有遞歸結構性質，

只不過鏈表太簡單了，它是一個線性結構，

所以可以使用非遞歸的方式，

如使用循環的方式就可以非常容易的解決鏈表的問題，

從鏈表開始就要打好遞歸的基礎，

對深入學習樹結構包括更加深刻的理解遞歸算法都是非常有好處的。

通過 leetcode 上與鏈表相關的問題來學習遞歸

在 leetcode 上提交鏈表相關的問題，

還有一些其它需要注意的地方，

與此同時在 leetcode 上解決與鏈表相關的問題，

思路在有一些地方和之前自自定義鏈表是不同的，

這里面的關鍵不同是在于有些情況下做這些程序

是以節點為中心的而不會包裝一個整體的鏈表類。

203 號問題：刪除鏈表中的元素

先找到這個鏈表中這個節點之前的那個節點，

但是對于頭節點來說沒有之前的那個節點，

所以就要特殊處理或者使用虛擬頭節點來統一這個操作。

ListNode

   // Definition for singly-linked list.
   public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
   }

Solution

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }

   */
  class Solution {

        public static ListNode removeElements(ListNode head, int val) {

  //        第一種方式 做對頭節點做特殊處理
  //        while (head != null && head.val == val) {
  //            ListNode delNode = head;
  //            head = head.next;
  //            delNode.next = null;
  //        }
  //
  //        if (head == null) {
  //            return head;
  //        }
  //
  //        ListNode prev = head;
  //        while (prev.next != null) {
  //            if (prev.next.val == val) {
  //                ListNode delNode = prev.next;
  //                prev.next = delNode.next;
  //                delNode.next = null;
  //            } else {
  //                prev = prev.next;
  //            }
  //        }
  //
  //        return head;

  //      第二種方式：添加虛擬頭節點
              ListNode dummyHead = new ListNode(0);
              dummyHead.next = head;
              ListNode node = dummyHead;
              while (node.next != null) {
                    if (node.next.val == val) {
                          node.next = node.next.next;
                    } else {
                          node = node.next;
                    }
              }

              return dummyHead.next;
        }
  }

## 自定義 203 號問題測試用例

1. 將數組轉換為鏈表
1. 鏈表的第一個節點就是你創建的這個節點，
2. 這個節點的值也是數組的第一個值，
3. 其它的節點通過第一個節點的 next 進行關聯，
4. 對應的值為數組中的每個值。

### 代碼示例

1. `(class: ListNode, class: Solution,`
1. `class: Solution2, class: Main)`
2. ListNode

  // Definition for singly-linked list.
  public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        // 構造函數，傳入一個數組，轉換成一個鏈表。
        public ListNode (int [] arr) {

              if (arr == null || arr.length == 0) {
                    throw new IllegalArgumentException("arr can not be empty.");
              }

              this.val = arr[0];
              ListNode cur = this;
              for (int i = 1; i < arr.length; i++) {
                    cur.next = new ListNode(arr[i]);
                    cur = cur.next;
              }
        }

        @Override
        public String toString () {

              StringBuilder sb = new StringBuilder();
              sb.append("LinkedList:");
              sb.append("[ ");
              for (ListNode cur = this; cur.next != null; cur = cur.next) {
                    sb.append(cur.val);
                    sb.append("->");
              }
              sb.append("NULL");
              sb.append(" ]");

              return sb.toString();
        }
  }

3. Solution

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) { val = x; }
   * }
   */
  class Solution {

        public ListNode removeElements(ListNode head, int val) {

  //        第一種方式 做對頭節點做特殊處理
              while (head != null && head.val == val) {
                    head = head.next;
              }

              if (head == null) {
                    return head;
              }

              ListNode prev = head;
              while (prev.next != null) {
                    if (prev.next.val == val) {
                          prev.next = prev.next.next;
                    } else {
                          prev = prev.next;
                    }
              }

              return head;
        }
  }

4. Solution2

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) { val = x; }
   * }
   */
  class Solution2 {

        public ListNode removeElements(ListNode head, int val) {

  //        第一種方式 做對頭節點做特殊處理
  //        while (head != null && head.val == val) {
  //            ListNode delNode = head;
  //            head = head.next;
  //            delNode.next = null;
  //        }
  //
  //        if (head == null) {
  //            return head;
  //        }
  //
  //        ListNode prev = head;
  //        while (prev.next != null) {
  //            if (prev.next.val == val) {
  //                ListNode delNode = prev.next;
  //                prev.next = delNode.next;
  //                delNode.next = null;
  //            } else {
  //                prev = prev.next;
  //            }
  //        }
  //
  //        return head;

  //      第二種方式：添加虛擬頭節點
              ListNode dummyHead = new ListNode(0);
              dummyHead.next = head;
              ListNode node = dummyHead;
              while (node.next != null) {
                    if (node.next.val == val) {
                          node.next = node.next.next;
                    } else {
                          node = node.next;
                    }
              }

              return dummyHead.next;
        }
  }

5. Main

  public class Main {

        public static void main(String[] args) {

           int[] arr = new int[20];

              for (int i = 0; i < 10 ; i++) {
                    arr[i] = i;
                    arr[10 + i] = 5;
              }

              ListNode  node1 = new ListNode(arr);
              System.out.println(node1);

              Solution s1 = new Solution();
              s1.removeElements(node1, 5);
              System.out.println(node1);

              ListNode  node2 = new ListNode(arr);
              System.out.println(node2);

              Solution2 s2 = new Solution2();
              s2.removeElements(node2, 5);
              System.out.println(node2);
        }
  }

## 鏈表和遞歸

1. 遞歸是極其重要的一種組建邏輯的機制
1. 尤其是在計算機的世界中
2. 對于高級的排序算法通常都需要使用遞歸，
3. 對于計算機科學來說熟練的掌握遞歸是極其重要的，
4. 甚至可以說初級水平與高級水平之間差距的關鍵分水嶺。
2. 遞歸可以做
1. 分形圖形的繪制，
2. 各種高級排序算法的可視化。

### 遞歸

1. 本質上就是將原來的問題，轉化為更小的同樣的一個問題
1. 也就是將問題規模逐漸縮小，小到一定程度，
2. 通常在遞歸中都是小到不能再小的時候就可以很容易的解決問題，
3. 這樣一來整個問題就可以得到解決。

### 遞歸的使用例子

1. 數組求和：求數組中 n 個元素的和

1. `Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])` 第一次，
2. `Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])` 第二次，
3. `...` 若干次
4. `Sum(arr[n-1...n-1]) = arr[n-1] + Sum(arr[])` 最后一次`
5. 每一次都是將同一個問題慢慢更小化從而演化成最基本的問題，
6. 最基本的問題解決了，然后根據之前的一些邏輯，從而解決原問題，
7. 就像一個大問題，如果他可以分解成無數個性質相同的小問題，
8. 然后對這些小問題以遞歸的形式進行處理，這樣一來就容易多了。
9. 代碼中`if (arr.length == cur) {return 0;}`就是解決最基本的問題
10.   代碼中`arr[cur] + sum(arr, cur+1);`就是在構建原問題的答案
11.   代碼中`sum(arr, cur+1);`就是不斷的將原問題轉化為更小的問題，
12.   很多個小問題的解加到一起，就構建出原問題的答案了。

  // 計算 arr[cur...n] 這個區間內的所有數字之和。
  public static int sum (int[] arr, int cur) {
        // 這個地方就是求解最基本問題
        // 通常對于遞歸算法來說，
        // 最基本的問題就是極其簡單的，
        // 基本上都是這樣的一種形式
        // 因為最基本的問題太過于平凡了
        // 一眼就看出來那個答案是多少了
        if (arr.length == cur) {
              return 0;
        }

        // 這部分就是遞歸算法最核心的部分
        // 把原問題轉化成更小的問題的一個過程
        // 這個過程是難的，
        // 這個轉化為更小的問題并不簡單的求一個更小的問題的答案就好了，
        // 而是要根據這個更小的問題的答案構建出原問題的答案，
        // 這個構建 在這里就是一個加法的過程。
        return arr[cur] + sum(arr, cur+1);
  }

2. 對于一個復雜的遞歸算法來說，
1. 這個邏輯可能是非常復雜的，
2. 雖然說轉化問題是一個難點，
3. 實際上也并不是那么難，
4. 只不過很多在寫邏輯的時候把自己給繞暈了，
5. 函數自己調用自己，不必過于糾結這里面程序執行的機制。
3. 寫遞歸函數的時候一定要注重遞歸函數本身的語意，
1. 例如上面的 sum 函數，
2. 它就是用來計算一個數組從索引 cur 開始
3. 到最后一個位置之間所有的數字之和，
4. 這個就是此遞歸函數的`“宏觀”語意`，
5. 在這樣的一個語意下，
6. 在涉及轉換邏輯的時候你要拋棄掉這是一個遞歸算法的這樣的想法，
7. 遞歸函數本身它也是一個函數，每個函數其實就是完成一個功能。
8. 在函數 A 中調函數 B 你并不會暈，但是在函數 A 里調用函數 A，
9. 也就是在遞歸函數中你可能就會暈，
10.   其實這和函數 A 里調用函數 B 在本質上并沒有區別。
4. 你可以當這是一個子邏輯，這個子邏輯里面需要傳兩個參數，
1. 它做的事情就是求數組里的從索引 cur 開始
2. 到最后一個位置之間所有的數字之和，
3. 你就僅僅是在用這個函數，至于或者函數是不是當前函數沒必要在意，
4. 其實就是這么簡單的一件事情。
5. 在寫遞歸算法的時候，
1. 有些時候不需要你特別微觀的
2. 陷進遞歸調用里的去糾結這個遞歸是怎么樣調用的，
3. 其實你可以直接把這個遞歸函數當成一個子函數，
4. 這個子函數可以完成特定的功能，
5. 而你要干的事情就是利用這個子函數來構建你自己的邏輯，
6. 來解決上層的這一個問題就好了。
6. 注意遞歸函數的`宏觀語意`
1. 把你要調用的遞歸函數當作是一個子函數或者子邏輯或者子過程，
2. 然后去想這個子過程如果去幫你解決現在的這個問題就 ok,
3. 要想熟練的掌握就需要大量的練習。

### 鏈表的天然遞歸結構性質

1. 代碼示例

  public class RecursionSolution {

        public ListNode removeElements(ListNode head, int val) {
              if (head == null) {
                    return null;
              }

  //        寫法一
  //        ListNode node = removeElements(head.next, val);
  //        if (head.val == val) {
  //            return 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;
              }
        }

     public static void main(String[] args) {

           int[] arr = {1, 10, 7, 5, 1, 9, 1, 5, 1, 5, 6, 7};

           ListNode  node = new ListNode(arr);
           System.out.println(node);

           RecursionSolution s = new RecursionSolution();
           s.removeElements(node, 1);
           System.out.println(node);
     }
  }

## 遞歸運行的機制及遞歸的“微觀”解讀

1. 雖然寫遞歸函數與遞歸算法時要注意遞歸算法的宏觀語意，
1. 但是站在一個更高的層面去思考這個函數它本身的功能作用是什么，
2. 也許可以幫助你更好的完成整個遞歸的邏輯，
3. 但是從另外一方面遞歸函數想，遞歸函數到底是怎樣運轉的，
4. 它內部的機制是怎樣的，所以遞歸的運行機制也是需要了解的。
2. 通過數組求和與刪除鏈表節點的遞歸實現來具體的觀察遞歸的運行機制
1. 棧的應用中說過程序調用的系統棧，
2. 子函數調用的位置會壓入到一個系統棧，
3. 當子函數調用完成的時候，
4. 程序就會從系統棧中找到上次父函數調用子函數的這個位置，
5. 然后再父函數中的子函數這個位置后續繼續執行，
6. 其實遞歸調用和子函數子過程的調用沒有區別，
7. 只不過遞歸調用的函數還是這個函數本身而已
8. (自己調用自己，根據某些條件終止調用自己)。
3. 遞歸的調用和子過程的調用是沒有區別的
1. 就像程序調用的系統棧一樣。
2. 父函數調用子函數，子函數執行完畢之后，
3. 就會返回到上一層，也就是繼續執行父函數，
4. 這個執行并不是重新執行，
5. 而是從之前那個子函數調用時的位置繼續往下執行，
6. 如果子函數有返回值，那么接收一下也可以，
7. 接收完了之后繼續往下執行。

  A0();
  function A0 () {
     ...
     A1();
     ...
  }
  function A1 () {
     ...
     A2();
     ...
  }
  function A2 () {
     ...
     ...
     ...
  }

4. 遞歸的調用時有代價的
1. 函數調用 + 系統棧空間。
2. 比如系統棧中會記錄這些函數調用的信息，
3. 如當前這個函數執行到哪兒了，
4. 當前的局部變量都是怎樣的一個狀態，
5. 然后給它壓入系統棧。，
6. 包括函數調用的本身在計算機的底層找到這個新的函數所在的位置，
7. 這些都是有一定的時間消耗的。
8. 遞歸調用的過程是很消耗系統棧的空間的，
9. 如果遞歸函數中沒有處理那個最基本的情況，
10.   那么遞歸將一直執行下去，不會正常終止，
11.   最終終止的結果肯定就是異常報錯，
12.   因為系統棧占滿了，空間不足。
13.   在線性的調用過程中，
14.   當你遞歸的次數達到十萬百萬級別的話，
15.   系統占還是會被占滿，因為存儲了太多函數調用的狀態信息。
5. 用遞歸書寫邏輯其實是更簡單的
1. 這一點在線性的結構中看不出來，
2. 這是因為線性的結構非常好想，
3. 直接寫循環就能解決所有的線性問題，
4. 但是一旦進入非線性的結構 如樹、圖，
5. 很多問題其實使用遞歸的方式解決將更加的簡單。

### 數組求和的遞歸解析

1. 原函數

  // 計算 arr[cur...n] 這個區間內的所有數字之和。
  public static int sum (int[] arr, int cur) {
        // 這個地方就是求解最基本問題
        // 通常對于遞歸算法來說，
        // 最基本的問題就是極其簡單的，
        // 基本上都是這樣的一種形式
        // 因為最基本的問題太過于平凡了
        // 一眼就看出來那個答案是多少了
        if (arr.length == cur) {
              return 0;
        }

        // 這部分就是遞歸算法最核心的部分
        // 把原問題轉化成更小的問題的一個過程
        // 這個過程是難的，
        // 這個轉化為更小的問題并不簡單的求一個更小的問題的答案就好了，
        // 而是要根據這個更小的問題的答案構建出原問題的答案，
        // 這個構建 在這里就是一個加法的過程。
        return arr[cur] + sum(arr, cur+1);
  }

2. 解析原函數

1. 遞歸函數的調用，本質就是就是函數調用，
2. 只不過調用的函數就是自己而已。

  // 計算 arr[cur...n] 這個區間內的所有數字之和。
  public static int sum (int[] arr, int cur) {

        if (arr.length == cur) {
              return 0;
        }

        int temp = sum(arr, cur + 1);
        int result = arr[cur] + temp;
        return result;
  }

3. 原函數解析 2

1. 在 sum 函數中調用到了 sum 函數，
2. 實際上是在一個新的 sum 函數中 調用邏輯，
3. 原來的 sum 函數中所有的變量保持不變，
4. 等新的 sum 函數執行完了邏輯，
5. 還會回到原來的 sum 函數中繼續執行余下的邏輯。

  // 計算 arr[cur...n] 這個區間內的所有數字之和。

  // 代號 001
  // 使用 arr = [6, 10]
  // 調用 sum(arr, 0)
  int sum (int[] arr, int cur) {

     if (cur == n) return 0; // n 為數組的長度：2

     int temp = sum(arr, cur + 1); // cur 為 0
     int result = arr[cur] + temp;
     return result;
  }

  // 代號 002
  // 到了 上面的sum(arr, cur + 1)時
  // 實際 調用了 sum(arr, 1)
  int sum (int[] arr, int cur) {

     if (cur == n) return 0; // n 為數組的長度：2

     int temp = sum(arr, cur + 1); // cur 為 1
     int result = arr[cur] + temp;
     return result;
  }

  // 代號 003
  // 到了 上面的sum(arr, cur + 1)時
  // 實際 調用了 sum(arr, 2)
  int sum (int[] arr, int cur) {

     // n 為數組的長度：2，cur 也為：2
     // 所以sum函數到這里就終止了
     if (cur == n) return 0;

     int temp = sum(arr, cur + 1); // cur 為 2
     int result = arr[cur] + temp;
     return result;
  }

  // 上面的代號003的sum函數執行完畢后 返回 0。
  //
  // 那么 上面的代號002的sum函數中
  // int temp = sum(arr, cur + 1)，temp獲取到的值 就為 0，
  // 然后繼續執行代號002的sum函數里temp獲取值時中斷的位置 下面的邏輯，
  // 執行到了int result = arr[cur] + temp，
  // temp為 0，cur 為 1，arr[1] 為 10，所以result 為 0 + 10 = 10，
  // 這樣一來 代號002的sum函數執行完畢了，返回 10。
  //
  // 那么 代號001的sum函數中
  // int temp = sum(arr, cur + 1)，temp獲取到的值 就為 10，
  // 然后繼續執行代號001的sum函數里temp獲取值時中斷的位置 下面的邏輯，
  // 執行到了int result = arr[cur] + temp，
  // temp為 10，cur 為 0，arr[0] 為 6，所以result 為 6 + 10 = 16，
  // 這樣一來 代號001的sum函數執行完畢了，返回 16。
  //
  // 代號001的sum函數沒有被其它代號00x的sum函數調用，
  // 所以數組求和的最終結果就是 16。

4. 調試遞歸函數的思路
1. 如果對遞歸函數運轉的機制不理解，
2. 不要對著遞歸函數去生看生想，
3. 在很多時候你肯定會越想越亂，
4. 不如你用一個非常小的測試數據集直接扔進這個函數中，
5. 你可以使用紙筆畫或者使用 IDE 提供的 debug 工具，
6. 一步一步的去看這個程序在每一步執行后計算的結果是什么，
7. 通常使用這種方式能夠幫助你更加清晰的理解程序的運轉邏輯，
8. 計算機是一門工科，和工程相關的科學，
9. 工程相關的科學雖然也注重理論它背后也有理論支撐，
10.   但是從工程的角度入手來實踐是非常非常重要的，
11.   很多時候你如果想理解它背后的理論，
12.   可能更好的方式不是去想這個理論，
13.   而是實際的去實踐一下看看這個過程到底是怎么回事兒。

### 刪除鏈表節點的遞歸解析

1. 原函數

  public ListNode removeElements(ListNode head, int val) {

           if (head == null) {
               return null;
           }

           head.next = removeElements(head.next, val);
           if (head.val == val) {
                 return head.next;
           } else {
                 return head;
           }
  }

2. 解析原函數

1. 遞歸調用的時候就是子過程的調用，
2. 一步一步的向下調用，調用完畢之后，
3. 子過程計算出結果后再一步一步的返回給上層的調用，
4. 最終得到了最終的結果，6->7->8->null 刪除掉 7 之后就是 6->8->null，
5. 節點真正的刪除是發生在步驟 3 中，
6. 在使用解決了一個更小規模的問題相應的解之后，
7. 結合當前的調用，組織邏輯，組織出了當前這個問題的解，
8. 就是這樣的一個過程。

  // 操作函數編號 001
  ListNode removeElements(ListNode head, int 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
  ListNode removeElements(ListNode head, int 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
  ListNode removeElements(ListNode head, int 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
  ListNode removeElements(ListNode head, int 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
  ListNode removeElements(ListNode head, int 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
  ListNode removeElements(ListNode head, int 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
  ListNode removeElements(ListNode head, int 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的節點都被剔除，操作完畢。

## 遞歸算法的調試

1. 可以以動畫的方式展示遞歸函數底層的運行機理，
1. 一幀一幀的動畫來展示遞歸函數的具體執行過程。
2. 但是在實際調試遞歸函數時
1. 很難畫出那么詳細的動畫，相對也比較費時間，
2. 但是也可以拿一張 A4 的白紙仔細的一下，
3. 例如 畫一個比較小的測試用例的執行過程是怎樣的，
4. 這樣對于理解你的程序或者找出你的程序中有錯誤，
5. 是非常有幫助的
3. 調試方法
1. 靠打印輸出，
2. 完全可以使用打印輸出的方式
3. 清楚的看出程序在執行過程中是怎樣一步一步獲得最終結果。
4. 單步跟蹤，
5. 也就是每一個 IDE 中自帶的調試功能。
6. 視情況來定。
4. 對于遞歸函數來說有一個非常重要的概念
1. 遞歸的深度，
2. 每一個函數在自己的內部都會去調用了一下自己，
3. 那么就代表每次調用自己時，整個遞歸的深度就多了 1，
4. 所以在具體的輸出可視化這個遞歸函數時，
5. 這個遞歸深度是可以幫助你理解這個遞歸過程的一個變量，
6. 在原遞歸函數中新增一個參數`depth`，
7. 根據這個變量生成遞歸深度字符串`--`，
8. `--`相同則代表同一遞歸深度。
5. 很多時候要想真正理解一個算法或者理解一個函數
1. 其實并沒有什么捷徑，肯定是要費一些勁，
2. 如果你不想在紙上畫出來的話，
3. 那么你就要用代碼畫出來，
4. 也就是要在代碼上添加很多的輔助代碼，
5. 這就是平時去理解程序或做練習時不要去犯懶，
6. 可能只要寫 4 行代碼就能解決問題，
7. 但是這背后很有可能是你寫了
8. 幾十行甚至上百行的代碼
9. 最終終于透徹的理解了這個程序，
10.   然后才能瀟灑的用四行代碼來解決這個問題。
6. 不停的練習如何寫一個遞歸的函數，才能理解理解這個遞歸的過程。

### 代碼示例 `(class: ListNode, class: RecursionSolution)`

1. ListNode

  // Definition for singly-linked list.
  public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        // 構造函數，傳入一個數組，轉換成一個鏈表。
        public ListNode (int [] arr) {

              if (arr == null || arr.length == 0) {
                    throw new IllegalArgumentException("arr can not be empty.");
              }

              this.val = arr[0];
              ListNode cur = this;
              for (int i = 1; i < arr.length; i++) {
                    cur.next = new ListNode(arr[i]);
                    cur = cur.next;
              }
        }

        @Override
        public String toString () {

              StringBuilder sb = new StringBuilder();
              sb.append("[ ");
              for (ListNode cur = this; cur != null; cur = cur.next) {
                    sb.append(cur.val);
                    sb.append("->");
              }
              sb.append("NULL");
              sb.append(" ]");

              return sb.toString();
        }
  }

2. RecursionSolution

  public class RecursionSolution {

        public ListNode removeElements(ListNode head, int val, int depth) {
  //        if (head == null) return null;
  //        head.next = removeElements(head.next, val, depth);
  //        return head.val == val ? head.next : head;

              String depathString = generateDepathString(depth);
              System.out.print(depathString);
              System.out.println("Call: remove " + val + " in " + head);

              if (head == null) {

                    System.out.print(depathString);
                    System.out.println("Return ：" + head);

                    return null;
              }

              ListNode result = removeElements(head.next, val, depth + 1);
              System.out.print(depathString);
              System.out.println("After： remove " + val + " ：" + result);

              ListNode ret;
              if (head.val == val) {
                    ret = result;
              } else {
                    head.next = result;
                    ret = head;
              }

              System.out.print(depathString);
              System.out.println("Return ：" + ret);

              return ret;

        }

        private String generateDepathString (int depath) {
              StringBuilder sb = new StringBuilder();
              for (int i = 0; i < depath; i++) {
                    sb.append("-- "); // -- 表示深度，--相同則代表在同一遞歸深度
              }
              return sb.toString();
        }

        public static void main(String[] args) {

              int[] arr = {6, 7, 8};

  //        for (int i = 0; i < 10 ; i++) {
  //            arr[i] = i;
  //            arr[10 + i] = 5;
  //        }

              ListNode  node = new ListNode(arr);
              System.out.println(node);

              RecursionSolution rs = new RecursionSolution();
              rs.removeElements(node, 7, 0);
              System.out.println(node);
        }
  }

## 更多與鏈表相關的問題

1. 關于遞歸
1. 鏈表有天然遞歸性質結構
2. 幾乎和鏈表相關的所有操作
1. 都可以使用遞歸的形式完成
3. 練習時可以對鏈表的增刪改查進行遞歸實現
1. 之前鏈表的增刪改查使用了循環的方式進行了實現，
2. 現在可以對鏈表的增刪改成進行遞歸的方式實現，
3. 這個練習是非常有意義的，能夠幫助你更好的理解遞歸。
4. 雖然實際使用鏈表時是不需要使用遞歸的，
5. 但是進行一下這種練習可以讓你更好的對遞歸有更深刻的理解。
4. 其它和鏈表相關的題目可以到 leetcode 上查找
1. 鏈表：`https://leetcode-cn.com/tag/linked-list/`，
2. 不要完美主義，不要想著把這些問題一下子全部做出來，
3. 根據自己的實際情況來制定計劃，在自己處于什么樣的水平的時候，
4. 完成怎樣的問題，但是這些問題一直都會在 leetcode 上，
5. 慢慢來，一點一點的實現。
5. 關于鏈表的技術研究，由斯坦福提出的問題研究
1. 文章地址：`https://max.book118.com/html/2017/0902/131359982.shtm`，
2. 都看懂了，那你就完全的懂了鏈表。
6. 非線性數據結構
1. 如大名鼎鼎的二分搜索樹
2. 二分搜索樹也是一個動態的數據結構
3. 也是靠節點掛接起來的，
4. 只不過那些節點沒有排成一根線，
5. 而是排成了一顆樹，
6. 不是每一個節點有指向下一個節點的 next，
7. 而是由指向左子樹和右子樹的兩個根節點而已。

### 雙鏈表

1. 對于隊列來說需要對鏈表的兩端進行操作
1. 在兩端進行操作的時候就遇到了問題，
2. 在尾端刪除元素，
3. 即使在尾端有 tail 的變量指向鏈表的結尾，
4. 它依然是一個`O(n)`復雜度的，。
5. 對于這個問題其實有一個解決方案，
6. 這個問題的解決方案就是雙鏈表，
2. 所謂的雙鏈表就是在鏈表中每一個節點包含兩個指針
1. 指針就代表著引用，
2. 有一個變量 next 指向這個節點的下一個節點，
3. 有一個變量 prev 指向這個節點的前一個節點，
4. 對于雙鏈表來說，
5. 你有了 tail 這個節點之后，
6. 刪除尾部的節點就非常簡單，
7. 而且這個操作會是`O(1)`級別的，
8. 但是代價是每一個節點從原來只有一個指針變為兩個指針，
9. 那么維護起來就會相對復雜一些。

  class Node {
     E e;
     Node next, prev;
  }

### 循環鏈表

1. 對于循環鏈表來說，也可以使用雙鏈表的思路來實現，
1. 不過需要設立一個虛擬的頭節點，
2. 從而讓整個鏈表形成了一個環，
3. 這里面最重要的是 尾節點不指向空而是指向虛擬頭節點，
4. 可以很方便的判斷某一個節點的下一個節點是否是虛擬頭節點
5. 來確定這個節點是不是尾節點，
6. 循環鏈表的好處是 進一步的把很多操作進行了統一，
7. 比如說在鏈表結尾添加元素只需要在 dummyHead 的前面
8. 添加要一個給元素，它就等于是在整個鏈表的結尾添加了一個元素，
9. 事實上循環鏈表本身是非常有用的，
10.   Java 中的 LinkedList 類底層的實現，本質就是一個循環鏈表，
11.   更準確一些，就是循環雙向鏈表，因為每個節點是有兩個指針的。

### 鏈表也是使用數組來實現

1. 因為鏈表的 next 只是指向下一個元素，
2. 在數組中每一個位置存儲的不僅僅是有這個元素，
3. 再多存儲一個指向下一個元素的索引，
4. 這個鏈表中每一個節點是這樣的，
5. Node 類中有一個 int 的變量 next 指向下一個元素的索引，
6. 在有一些情況下，比如你明確的知道你要處理的元素有多少個，
7. 這種時候使用這種數組鏈表有可能是更加方便的。

class Node {

  E e;
  int next;

}