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

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

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

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

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

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

并且也依托鏈表這樣的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了棧和隊(duì)列，

在實(shí)現(xiàn)隊(duì)列的時(shí)候?qū)︽湵磉M(jìn)行了一些改進(jìn)。

遞歸不光用于樹這樣的結(jié)構(gòu)中還可以用在鏈表這樣的結(jié)構(gòu)中

鏈表本身就天然的具有遞歸結(jié)構(gòu)性質(zhì)，

只不過鏈表太簡單了，它是一個(gè)線性結(jié)構(gòu)，

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

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

從鏈表開始就要打好遞歸的基礎(chǔ)，

對(duì)深入學(xué)習(xí)樹結(jié)構(gòu)包括更加深刻的理解遞歸算法都是非常有好處的。

通過 leetcode 上與鏈表相關(guān)的問題來學(xué)習(xí)遞歸

在 leetcode 上提交鏈表相關(guān)的問題，

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

與此同時(shí)在 leetcode 上解決與鏈表相關(guān)的問題，

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

這里面的關(guān)鍵不同是在于有些情況下做這些程序

是以節(jié)點(diǎn)為中心的而不會(huì)包裝一個(gè)整體的鏈表類。

203 號(hào)問題：刪除鏈表中的元素

先找到這個(gè)鏈表中這個(gè)節(jié)點(diǎn)之前的那個(gè)節(jié)點(diǎn)，

但是對(duì)于頭節(jié)點(diǎn)來說沒有之前的那個(gè)節(jié)點(diǎn)，

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

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

  //        第一種方式 做對(duì)頭節(jié)點(diǎn)做特殊處理
  //        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é)點(diǎn)
              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 號(hào)問題測(cè)試用例

1. 將數(shù)組轉(zhuǎn)換為鏈表
1. 鏈表的第一個(gè)節(jié)點(diǎn)就是你創(chuàng)建的這個(gè)節(jié)點(diǎn)，
2. 這個(gè)節(jié)點(diǎn)的值也是數(shù)組的第一個(gè)值，
3. 其它的節(jié)點(diǎn)通過第一個(gè)節(jié)點(diǎn)的 next 進(jìn)行關(guān)聯(lián)，
4. 對(duì)應(yīng)的值為數(shù)組中的每個(gè)值。

### 代碼示例

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

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

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

  //        第一種方式 做對(duì)頭節(jié)點(diǎn)做特殊處理
  //        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é)點(diǎn)
              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. 遞歸是極其重要的一種組建邏輯的機(jī)制
1. 尤其是在計(jì)算機(jī)的世界中
2. 對(duì)于高級(jí)的排序算法通常都需要使用遞歸，
3. 對(duì)于計(jì)算機(jī)科學(xué)來說熟練的掌握遞歸是極其重要的，
4. 甚至可以說初級(jí)水平與高級(jí)水平之間差距的關(guān)鍵分水嶺。
2. 遞歸可以做
1. 分形圖形的繪制，
2. 各種高級(jí)排序算法的可視化。

### 遞歸

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

### 遞歸的使用例子

1. 數(shù)組求和：求數(shù)組中 n 個(gè)元素的和

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

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

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

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

### 鏈表的天然遞歸結(jié)構(gòu)性質(zhì)

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

## 遞歸運(yùn)行的機(jī)制及遞歸的“微觀”解讀

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

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

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

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

1. 原函數(shù)

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

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

2. 解析原函數(shù)

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

  // 計(jì)算 arr[cur...n] 這個(gè)區(qū)間內(nèi)的所有數(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ù)中調(diào)用到了 sum 函數(shù)，
2. 實(shí)際上是在一個(gè)新的 sum 函數(shù)中 調(diào)用邏輯，
3. 原來的 sum 函數(shù)中所有的變量保持不變，
4. 等新的 sum 函數(shù)執(zhí)行完了邏輯，
5. 還會(huì)回到原來的 sum 函數(shù)中繼續(xù)執(zhí)行余下的邏輯。

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

  // 代號(hào) 001
  // 使用 arr = [6, 10]
  // 調(diào)用 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;
  }

  // 代號(hào) 002
  // 到了 上面的sum(arr, cur + 1)時(shí)
  // 實(shí)際 調(diào)用了 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;
  }

  // 代號(hào) 003
  // 到了 上面的sum(arr, cur + 1)時(shí)
  // 實(shí)際 調(diào)用了 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;
  }

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

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

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

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

  // 操作函數(shù)編號(hào) 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;
  }
  // 模擬調(diào)用，對(duì) 6->7->8->null 進(jìn)行7的刪除
  // 調(diào)用 removeElments(head, 7);
  // 執(zhí)行步驟1，head當(dāng)前的節(jié)點(diǎn)為6，既然不為null，所以不返回null，
  // 繼續(xù)執(zhí)行步驟2，head.next = removeElements(head.next, 7)，
  // 求當(dāng)前節(jié)點(diǎn)后面的一個(gè)節(jié)點(diǎn)，后面的一個(gè)節(jié)點(diǎn)目前不知道，
  // 但是可以通過removeElements(head.next, 7)這樣的子過程調(diào)用求出來，
  // 這次傳入的是當(dāng)前節(jié)點(diǎn)的next，也就是7的這個(gè)節(jié)點(diǎn)，7->8->null。

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

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

  // 操作函數(shù)編號(hào) 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;
  }
  // 模擬調(diào)用，對(duì) null 進(jìn)行7的刪除
  // 調(diào)用 removeElements(head.next, 7);
  // head.next 會(huì)被賦值給 函數(shù)中的局部變量 head，
  // 也就是調(diào)用時(shí)被轉(zhuǎn)換為 removeElements(head, 7);
  // 執(zhí)行步驟1，head當(dāng)前的節(jié)點(diǎn)為null，直接返回null，不繼續(xù)向下執(zhí)行了。

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

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

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

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

## 遞歸算法的調(diào)試

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

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

1. ListNode

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

        // 構(gòu)造函數(shù)，傳入一個(gè)數(shù)組，轉(zhuǎn)換成一個(gè)鏈表。
        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);
        }
  }

## 更多與鏈表相關(guān)的問題

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

### 雙鏈表

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

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

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

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

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

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

class Node {

  E e;
  int next;

}