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

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

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

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

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

已經(jīng)從底層完整實現(xiàn)了一個單鏈表這樣的數(shù)據(jù)結構，

并且也依托鏈表這樣的數(shù)據(jù)結構實現(xiàn)了棧和隊列，

在實現(xiàn)隊列的時候對鏈表進行了一些改進。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

先找到這個鏈表中這個節(jié)點之前的那個節(jié)點，

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

所以就要特殊處理或者使用虛擬頭節(jié)點來統(tǒng)一這個操作。

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) {

  //        第一種方式 做對頭節(jié)點做特殊處理
  //        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;

  //      第二種方式：添加虛擬頭節(jié)點
              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. 將數(shù)組轉換為鏈表
1. 鏈表的第一個節(jié)點就是你創(chuàng)建的這個節(jié)點，
2. 這個節(jié)點的值也是數(shù)組的第一個值，
3. 其它的節(jié)點通過第一個節(jié)點的 next 進行關聯(lián)，
4. 對應的值為數(shù)組中的每個值。

### 代碼示例

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; }

        // 構造函數(shù)，傳入一個數(shù)組，轉換成一個鏈表。
        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) {

  //        第一種方式 做對頭節(jié)點做特殊處理
              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) {

  //        第一種方式 做對頭節(jié)點做特殊處理
  //        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;

  //      第二種方式：添加虛擬頭節(jié)點
              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. 也就是將問題規(guī)模逐漸縮小，小到一定程度，
2. 通常在遞歸中都是小到不能再小的時候就可以很容易的解決問題，
3. 這樣一來整個問題就可以得到解決。

### 遞歸的使用例子

1. 數(shù)組求和：求數(shù)組中 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. 最基本的問題解決了，然后根據(jù)之前的一些邏輯，從而解決原問題，
7. 就像一個大問題，如果他可以分解成無數(shù)個性質相同的小問題，
8. 然后對這些小問題以遞歸的形式進行處理，這樣一來就容易多了。
9. 代碼中`if (arr.length == cur) {return 0;}`就是解決最基本的問題
10.   代碼中`arr[cur] + sum(arr, cur+1);`就是在構建原問題的答案
11.   代碼中`sum(arr, cur+1);`就是不斷的將原問題轉化為更小的問題，
12.   很多個小問題的解加到一起，就構建出原問題的答案了。

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

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

2. 對于一個復雜的遞歸算法來說，
1. 這個邏輯可能是非常復雜的，
2. 雖然說轉化問題是一個難點，
3. 實際上也并不是那么難，
4. 只不過很多在寫邏輯的時候把自己給繞暈了，
5. 函數(shù)自己調用自己，不必過于糾結這里面程序執(zhí)行的機制。
3. 寫遞歸函數(shù)的時候一定要注重遞歸函數(shù)本身的語意，
1. 例如上面的 sum 函數(shù)，
2. 它就是用來計算一個數(shù)組從索引 cur 開始
3. 到最后一個位置之間所有的數(shù)字之和，
4. 這個就是此遞歸函數(shù)的`“宏觀”語意`，
5. 在這樣的一個語意下，
6. 在涉及轉換邏輯的時候你要拋棄掉這是一個遞歸算法的這樣的想法，
7. 遞歸函數(shù)本身它也是一個函數(shù)，每個函數(shù)其實就是完成一個功能。
8. 在函數(shù) A 中調函數(shù) B 你并不會暈，但是在函數(shù) A 里調用函數(shù) A，
9. 也就是在遞歸函數(shù)中你可能就會暈，
10.   其實這和函數(shù) A 里調用函數(shù) B 在本質上并沒有區(qū)別。
4. 你可以當這是一個子邏輯，這個子邏輯里面需要傳兩個參數(shù)，
1. 它做的事情就是求數(shù)組里的從索引 cur 開始
2. 到最后一個位置之間所有的數(shù)字之和，
3. 你就僅僅是在用這個函數(shù)，至于或者函數(shù)是不是當前函數(shù)沒必要在意，
4. 其實就是這么簡單的一件事情。
5. 在寫遞歸算法的時候，
1. 有些時候不需要你特別微觀的
2. 陷進遞歸調用里的去糾結這個遞歸是怎么樣調用的，
3. 其實你可以直接把這個遞歸函數(shù)當成一個子函數(shù)，
4. 這個子函數(shù)可以完成特定的功能，
5. 而你要干的事情就是利用這個子函數(shù)來構建你自己的邏輯，
6. 來解決上層的這一個問題就好了。
6. 注意遞歸函數(shù)的`宏觀語意`
1. 把你要調用的遞歸函數(shù)當作是一個子函數(shù)或者子邏輯或者子過程，
2. 然后去想這個子過程如果去幫你解決現(xiàn)在的這個問題就 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. 雖然寫遞歸函數(shù)與遞歸算法時要注意遞歸算法的宏觀語意，
1. 但是站在一個更高的層面去思考這個函數(shù)它本身的功能作用是什么，
2. 也許可以幫助你更好的完成整個遞歸的邏輯，
3. 但是從另外一方面遞歸函數(shù)想，遞歸函數(shù)到底是怎樣運轉的，
4. 它內部的機制是怎樣的，所以遞歸的運行機制也是需要了解的。
2. 通過數(shù)組求和與刪除鏈表節(jié)點的遞歸實現(xiàn)來具體的觀察遞歸的運行機制
1. 棧的應用中說過程序調用的系統(tǒng)棧，
2. 子函數(shù)調用的位置會壓入到一個系統(tǒng)棧，
3. 當子函數(shù)調用完成的時候，
4. 程序就會從系統(tǒng)棧中找到上次父函數(shù)調用子函數(shù)的這個位置，
5. 然后再父函數(shù)中的子函數(shù)這個位置后續(xù)繼續(xù)執(zhí)行，
6. 其實遞歸調用和子函數(shù)子過程的調用沒有區(qū)別，
7. 只不過遞歸調用的函數(shù)還是這個函數(shù)本身而已
8. (自己調用自己，根據(jù)某些條件終止調用自己)。
3. 遞歸的調用和子過程的調用是沒有區(qū)別的
1. 就像程序調用的系統(tǒng)棧一樣。
2. 父函數(shù)調用子函數(shù)，子函數(shù)執(zhí)行完畢之后，
3. 就會返回到上一層，也就是繼續(xù)執(zhí)行父函數(shù)，
4. 這個執(zhí)行并不是重新執(zhí)行，
5. 而是從之前那個子函數(shù)調用時的位置繼續(xù)往下執(zhí)行，
6. 如果子函數(shù)有返回值，那么接收一下也可以，
7. 接收完了之后繼續(xù)往下執(zhí)行。

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

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

### 數(shù)組求和的遞歸解析

1. 原函數(shù)

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

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

2. 解析原函數(shù)

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

  // 計算 arr[cur...n] 這個區(qū)間內的所有數(shù)字之和。
  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. 原函數(shù)解析 2

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

  // 計算 arr[cur...n] 這個區(qū)間內的所有數(shù)字之和。

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

     if (cur == n) return 0; // n 為數(shù)組的長度：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 為數(shù)組的長度：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 為數(shù)組的長度：2，cur 也為：2
     // 所以sum函數(shù)到這里就終止了
     if (cur == n) return 0;

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

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

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

### 刪除鏈表節(jié)點的遞歸解析

1. 原函數(shù)

  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. 解析原函數(shù)

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

  // 操作函數(shù)編號 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);
  // 執(zhí)行步驟1，head當前的節(jié)點為6，既然不為null，所以不返回null，
  // 繼續(xù)執(zhí)行步驟2，head.next = removeElements(head.next, 7)，
  // 求當前節(jié)點后面的一個節(jié)點，后面的一個節(jié)點目前不知道，
  // 但是可以通過removeElements(head.next, 7)這樣的子過程調用求出來，
  // 這次傳入的是當前節(jié)點的next，也就是7的這個節(jié)點，7->8->null。

  // 操作函數(shù)編號 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 會被賦值給 函數(shù)中的局部變量 head，
  // 也就是調用時被轉換為 removeElements(head, 7);
  // 執(zhí)行步驟1，head當前的節(jié)點為7，不為null，所以也不會返回null，
  // 繼續(xù)執(zhí)行步驟2，head.next = removeElements(head.next, 7)，
  // 求當前節(jié)點后面的一個節(jié)點，后面的一個節(jié)點目前不知道，
  // 但是可以通過removeElements(head.next, 7)這樣的子過程調用求出來，
  // 這次傳入的也是當前節(jié)點的next，也就是8的這個節(jié)點，8->null。

  // 操作函數(shù)編號 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 會被賦值給 函數(shù)中的局部變量 head，
  // 也就是調用時被轉換為 removeElements(head, 7);
  // 執(zhí)行步驟1，head當前的節(jié)點為7，不為null，所以也不會返回null，
  // 繼續(xù)執(zhí)行步驟2，head.next = removeElements(head.next, 7)，
  // 求當前節(jié)點后面的一個節(jié)點，后面的一個節(jié)點目前不知道，
  // 但是可以通過removeElements(head.next, 7)這樣的子過程調用求出來，
  // 這次傳入的也是當前節(jié)點的next，也就是null的這個節(jié)點，null。

  // 操作函數(shù)編號 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 會被賦值給 函數(shù)中的局部變量 head，
  // 也就是調用時被轉換為 removeElements(head, 7);
  // 執(zhí)行步驟1，head當前的節(jié)點為null，直接返回null，不繼續(xù)向下執(zhí)行了。

  // 操作函數(shù)編號 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;
  }
  // 這時候回到操作函數(shù)編號 004的上一層中來，
  // 操作函數(shù)編號 003 調用到了步驟2，并且head.next接收到的返回值為null,
  // 繼續(xù)操作函數(shù)編號 003 的步驟3，判斷當前節(jié)點的val是否為7，
  // 很明顯函數(shù)編號003里的當前節(jié)點的val為8，所以返回當前的節(jié)點 8->null。

  // 操作函數(shù)編號 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;
  }
  // 這時候回到操作函數(shù)編號 003的上一層中來，
  // 操作函數(shù)編號 002 調用到了步驟2，head.next接收到的返回值為節(jié)點 8->null，
  // 繼續(xù)操作函數(shù)編號 002 的步驟3，判斷當前節(jié)點的val是否為7，
  // 此時函數(shù)編號 002 的當前節(jié)點的val為7，所以返回就是當前節(jié)點的next 8->null，
  // 也就是說不返回當前的節(jié)點 head：7->8->null ，改返回當前節(jié)點的下一個節(jié)點，
  // 這樣一來就相當于刪除了當前這個節(jié)點，改讓父節(jié)點的next指向當前節(jié)點的next。

  // 操作函數(shù)編號 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;
  }
  // 這時候回到操作函數(shù)編號 002的上一層中來，
  // 操作函數(shù)編號 001 調用到了步驟2，head.next接收到的返回值為節(jié)點 8->null，
  // 繼續(xù)操作函數(shù)編號 001 的步驟3，判斷當前節(jié)點的val是否為7，
  // 函數(shù)編號 001 中當前節(jié)點的val為6，所以返回當前的節(jié)點 head：6->8->null，
  // 之前當前節(jié)點 為head：6->7->8->null，由于head.next在步驟2時發(fā)生了改變，
  // 原來老的head.next（head：7->8->null） 從鏈表中剔除了，
  // 所以當前節(jié)點 為head：6->8->null。

  // 鏈表中包含節(jié)點的val為7的節(jié)點都被剔除，操作完畢。

## 遞歸算法的調試

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

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

1. ListNode

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

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

### 雙鏈表

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

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

### 循環(huán)鏈表

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

### 鏈表也是使用數(shù)組來實現(xiàn)

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

class Node {

  E e;
  int next;

}