【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-链表与递归
前言
【从蛋壳到满天飞】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 上解决与链表相关的问题，
- 思路在有一些地方和之前自自定义链表是不同的，
- 这里面的关键不同是在于有些情况下做这些程序
- 是以节点为中心的而不会包装一个整体的链表类。
leetcode 上与链表相关的问题
-
203 号问题：删除链表中的元素
- 先找到这个链表中这个节点之前的那个节点，
- 但是对于头节点来说没有之前的那个节点，
- 所以就要特殊处理或者使用虚拟头节点来统一这个操作。
代码示例 (class: ListNode, class: Solution)
-
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;
}
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
