# 链表简介
前面我们分别介绍了三种线性数据结构，分别是动态数组、栈、队列。底层都是依托静态数组，靠resize解决固定容量问题。下面我们简单来介绍下链表这种数据结构。
链表是一种真正的动态数据结构，也是最简单的动态数据结构，学好链表可以帮我们更好的学习后面的二分搜索树、平衡二叉树、红黑树、AVL树等动态数据结构。链表可以帮我们更深入的理解引用（或者指针），链表有着非常清晰的递归结构，可以帮助我们更加深入的理解递归。链表还可以辅助组成其他数据结构，如哈希表等。
链表中的数据存储在节点中，通过next指向下一个数据。
链表的优点：链表是真正的动态数据结构，不需要处理固定容量的问题，对于链表来说，需要存储多少数据，生成对应的节点，把它们挂接起来就行
链表的缺点：丧失了随机访问的能力，不能像数组一样通过索引直接拿到对应的元素。这是因为数组所开辟的空间在内存中是连续分布的，可以直接通过这个索引对应的偏移直接计算出这个数据所存储的内存地址，直接用O(1)的复杂度就能把数据取出。但是链表不同，链表是靠next一层一层链接的，在计算机的底层每个节点所在的内存的位置是不同的，必须靠next一个一个的找到要找的元素。
链表中的数据在内存中是散落分布的：
# 数组和链表的对比
数组最好用于索引有语义的情况，最大的优点支持快速查询。链表不适合用于索引有语义的情况，最大的有点是动态。
# 链表的简单实现
链表是由一个一个节点组成的，每个节点包含两个属性，分别是值和指向下一个元素的next引用。因为节点是属于链表的，所以我们设计两个类，分别为LinkedList和Node。
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
// 方便后续的打印输出
@Override
public String toString(){
return e.toString();
}
}
}
上面我们简单实现了组成链表的节点类，下面我们来实现链表中的一些常用方法。
我们要想访问链表中所有的节点，就需要把链表的头存储起来，通常链表的头叫head，所以我们需要声明一个节点head，除此之外我们还需要记录链表中存储的节点个数。
// head节点
private Node head;
// 存储链表中节点个数
private int size;
获取链表中的元素个数和判断链表是否为空比较简单，这里直接给出
// 获取链表中的元素个数
public int getSize(){
return size;
}
// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
# 在链表头部插入节点
下面我们来实现给链表添加节点的功能，给链表添加节点分为在链表头部添加节点和在链表中间添加节点。对于数组来说在数组尾部添加元素是很简单的，但对于链表来说却是给链表头部添加节点更简单。因为对于链表我们有个head变量在记录链表的头，但没有变量记录链表的尾部。
如图，如果我们想把节点0插入到链表的头部，只需要将节点0的next指向节点head，并将节点0赋值给head即可。
// 在链表头添加新的元素e
public void addFirst(E e){
Node node = new Node(e);
node.next = head;
head = node;
size ++;
}
上面的代码可以优化如下：
public void addFirst(E e){
head = new Node(e, head);
size ++;
}
当我们执行new Node(e, head)时，会执行Node类的构造函数，将head传给构造函数的next并创建一个node节点，此时新创建节点的next就指向了head，head = new Node(e, head)将head指向了这个新节点。
# 在链表中间插入元素
如图，我们想将node节点插入到索引为2的地方，需要先找到要添加节点位置的前的一个节点也就是prev节点，然后将node节点的next指向prev指向的下一个节点，再将prev节点的next指向node节点即可。
注意在链表的操作过程中顺序是很重要的，这个例子中节点指向不能写成这样：
prev.next = node
node = prev.next
上面这样写，prev.next已经指向了node节点，再将node节点指向node节点本身。
下面我们来实现下向链表中特定位置插入节点的方法：
public void add(int index, E e){
// index > size 表示index是可以取到size的也就是向链表的末尾添加节点
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
// 向链表头添加一个节点
if(index == 0)
addFirst(e);
else{
Node prev = head;
// index - 1 表示找index位置的前一个位置的节点
for(int i = 0 ; i < index - 1 ; i ++)
// prev一直向前移动，一直移动到index-1这个位置，也就是要插入位置的前一个节点
prev = prev.next;
// 插入节点
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
// 上面三行插入相关的代码可以简写如下，表示先新建一个节点然后将这个新节点的next指向prev.next，再将prev.next指向这个新节点：
prev.next = new Node(e, prev.next);
size ++;
}
}
# 向链表末尾插入节点
由于上面我们已将实现了向链表中插入节点的add方法，向链表末尾插入节点可以直接调用add方法完成添加。
public void addLast(E e){
add(size, e);
}
上述所实现方法的完整代码如下：
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
// 存储链表头
private Node head;
// 记录链表中一共存储了多少元素
private int size;
public LinkedList(){
head = null;
size = 0;
}
// 获取链表中的元素个数
public int getSize(){
return size;
}
// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
// 在链表头添加新的元素e
public void addFirst(E e){
// Node node = new Node(e);
// node.next = head;
// head = node;
head = new Node(e, head);
size ++;
}
// 在链表的index(0-based)位置添加新的元素e
// 在链表中不是一个常用的操作，练习用：）
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
if(index == 0)
addFirst(e);
else{
Node prev = head;
for(int i = 0 ; i < index - 1 ; i ++)
prev = prev.next;
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
prev.next = new Node(e, prev.next);
size ++;
}
}
// 在链表末尾添加新的元素e
public void addLast(E e){
add(size, e);
}
}
# 链表虚拟头节点
前面我们实现了向链表中添加节点的add方法，其中对向链表头添加元素做了特殊处理
public void add(int index, E e){
// ...
// 向链表头添加元素
if(index == 0)
addFirst(e);
else{
// ...
}
}
为什么向链表头添加元素要做特殊处理呢？是因为我们向链表中添加节点时需要找到待添加位置之前的那个节点，但是对于链表头来说它没有前面的那个节点，所以逻辑上会特殊处理。
在链表的具体实现中有一个非常常用的技巧，可以将链表头的操作和其他操作统一起来。链表头之所以要链表头不是没有前置节点吗，我们就造一个前置节点，它不存储任意元素，将这个空节点当做链表的头也就是虚拟头节点。这样对于链表来说第一个元素就是这个空节点next所指向的节点，这个空节点只是为了便于编写代码。
代码实现：
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
// 虚拟头节点
private Node dummyHead;
private int size;
public LinkedList(){
// 此时对于一个空的链表来说它是存在一个节点的
dummyHead = new Node();
size = 0;
}
// 获取链表中的元素个数
public int getSize(){
return size;
}
// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
// 在链表的index(0-based)位置添加新的元素e
// 在链表中不是一个常用的操作，练习用：）
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
// 初始是从dummyHead开始的，指向的是0这个节点之前的节点
Node prev = dummyHead;
// 因为是从dummyHead开始的所以需要遍历index次
for(int i = 0 ; i < index ; i ++)
prev = prev.next;
prev.next = new Node(e, prev.next);
size ++;
}
// 在链表头添加新的元素e
public void addFirst(E e){
add(0, e);
}
// 在链表末尾添加新的元素e
public void addLast(E e){
add(size, e);
}
}
# 链表的遍历、查询和修改
下面来实现获取链表中第index位置的元素，由于在链表中不常使用索引，所以这个方法只是个练习，为了更好的熟悉操作链表。
前面我们已经实现了给链表指定位置添加元素的add方法，现在我们要实现的是获取指定元素的方法，添加元素是遍历的链表中index位置的前一个元素，获取元素是获取index位置的元素，操作方法类似，只需要将add方法稍作修改即可。
// 获得链表的第index(0-based)个位置的元素
// 在链表中不是一个常用的操作，练习用：）
public E get(int index){
// 判断index的合法性
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Illegal index.");
// 从索引为零的位置开始
Node cur = dummyHead.next;
// 遍历index次
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
return cur.e;
}
下面实现获取链表中第一个元素及最后一个元素的方法，可以直接调用上面的get方法，这里直接列出
// 获得链表的第一个元素
public E getFirst(){
return get(0);
}
// 获得链表的最后一个元素
public E getLast(){
return get(size - 1);
}
修改指定位置的元素和获取的逻辑基本类似，只不过一个找节点后返回，一个是给这个节点重新赋值
// 修改链表的第index(0-based)个位置的元素为e
// 在链表中不是一个常用的操作，练习用：）
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Illegal index.");
Node cur = dummyHead.next;
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
cur.e = e;
}
查找链表中是否包含指定节点，思路：从链表开头依次遍历到链表末尾，看看其中是否有节点和这个节点相等，如果相等返回true，如果没有就返回false。
// 查找链表中是否有元素e
public boolean contains(E e){
Node cur = dummyHead.next;
while(cur != null){
if(cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
# 从链表中删除元素
查找到待删除节点的前一个节点prev，然后将pre.next指向待删除节点的next，也就是跳过这个待删除的节点，这样操作后，因为遍历不到这个待删除的节点了，也就等同于将这个节点删除了。为了方便计算机回收这个待删除的节点的空间需要将delNode.next指向null，使它和整个链表脱离开。
删除指定位置的节点代码实现：
// 从链表中删除index(0-based)位置的元素, 返回删除的元素
// 在链表中不是一个常用的操作，练习用：）
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
// 找到待删除节点之前的节点，所以prev是从dummyHead开始
Node prev = dummyHead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;
// 删除节点
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size --;
return retNode.e;
}
从链表中删除第一个节点、从链表中删除最后一个节点
// 从链表中删除第一个元素, 返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从链表中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size - 1);
}
// 从链表中删除元素e
public void removeElement(E e){
Node prev = dummyHead;
while(prev.next != null){
if(prev.next.e.equals(e))
break;
prev = prev.next;
}
if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
}
}
下面展示一个错误的删除逻辑：
用cur变量找到要删除的节点，然后将cur指向cur.next这个节点，这样并不能删除待删除的节点，只不过是将变量cur指向了待删除节点的下一个节点而已。如果想让链表发生改变，必须把链表中相应节点的next做变化，而不是让某个一节点变量发生变化。
# 链表的时间复杂度分析
| 方法名 | 时间复杂度 | 备注 |
|---|---|---|
| addLast(e) | O(n) | |
| addFirst(e) | O(1) | |
| add(index, e) | O(n) | |
| removeLast(e) | O(n) | |
| removeFirst(e) | O(1) | |
| remove(index, e) | O(n) | |
| set(index, e) | O(n) | |
| get(index) | O(n) | |
| contains(e) | O(n) |
对于链表来说，增、删、改、查这四个操作它的时间复杂度都是O(n)的，但是如果我们只对链表头进行操作它的时间复杂度是O(1)级别的。由于链表整体是动态的，所以不会大量的浪费内存空间，链表是一种最基础的动态数据结构，熟练掌握链表，对于学习其他动态的数据结构有很大帮助。
# 使用链表实现栈
如果我们只对链表的头进行增、删的话时间复杂度是O(1)的，如果我们只查链表头的元素，时间复杂度也是O(1)的。是不是和之前介绍栈这种数据结构类似呢。所以对应链表，我们可以将链表头当做栈顶，用链表作为栈的底层实现，来实现栈这种的数据结构。
由于用链表实现栈这种数据结构都是调用的上面我们提到的链表操作方法，这里直接给出具体实现代码：
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> list;
// 因为链表没有容积这个概念，所以构造函数只有这一个就够了
public LinkedListStack(){
list = new LinkedList<>();
}
@Override
public int getSize(){
return list.getSize();
}
@Override
public boolean isEmpty(){
return list.isEmpty();
}
@Override
public void push(E e){
list.addFirst(e);
}
@Override
public E pop(){
return list.removeFirst();
}
@Override
public E peek(){
return list.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: top ");
res.append(list);
return res.toString();
}
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
for(int i = 0 ; i < 5 ; i ++){
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
}
上面我们用链表实现了栈这种数据结构，之前我们用数组也实现了栈这种数据结构，那么这两种实现方式哪种更好呢？
测试两种实现栈方法的性能：
import java.util.Random;
public class Main {
// 测试使用stack运行opCount个push和pop操作所需要的时间，单位：秒
private static double testStack(Stack<Integer> stack, int opCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i = 0 ; i < opCount ; i ++)
stack.push(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
stack.pop();
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
ArrayStack<Integer> arrayStack = new ArrayStack<>();
double time1 = testStack(arrayStack, opCount);
System.out.println("ArrayStack, time: " + time1 + " s");
LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
double time2 = testStack(linkedListStack, opCount);
System.out.println("LinkedListStack, time: " + time2 + " s");
// 其实这个时间比较很复杂，因为LinkedListStack中包含更多的new操作
}
}
链表实现的栈要比数组实现栈速度更快些。因为对于数组栈来说需要resize，这个过程是比较耗时的，而链表栈并不存在这种情况。但这个结果不是一定的，因为对于链表栈来说要不停的new Node，包含更多的new操作，new操作在不同的系统上可能比较耗时，因为在不停的在寻找开辟空间的地方，通常操作越多，new操作耗时越明显。实际上不管是Array stack还是链表栈它们的各项操作在实现中都是同一复杂度的，它们之间没有复杂度上的巨大差异。
# 使用链表实现队列
前面我们使用链表实现了栈这种数据结构，那么能不能使用链表实现队列这种数据结构呢？
前面我们知道对于链表头的增删时间复杂度是O(1)级别的，对于链表尾部的操作时间复杂度是O(n)级别的。可见用链表实现队列，队列的一端时间复杂度会是O(n)级别的。
有没有什么方法可以优化下呢？
这里我们思考下为什么说在链表头部增删元素比较简单呢？这是因为我们有head这样一个变量帮我们标记链表的头在哪，这样的话是否可以有个变量来记录链表尾部的位置呢？如果有了这个标记尾部的变量那在链表尾部添加节点就会变的很容易，但是对于从链表尾部删除一个节点还是比较复杂的，因为需要找到待删除节点的前一个节点。
综上，当我们分别有一个变量标记链表的头部，一个变量标记链表的尾部时，对于链表头部的操作时间复杂度都是O(1)级别的，对于链表尾部只有增加节点的时间复杂度是O(1)级别的。这样看来我们可以用链表的头部当做队首负责出队，用链表的尾部当做队尾负责入队。
由于我们只对队尾和队首进行操作，不涉及对中间元素进行操作，所以链表不必包含虚拟头节点，但是这样要注意链表为空的情况，也就是链表头部和尾部都指向空。
实现入队操作：
public void enqueue(E e){
// tail为空，说明链表为空
if(tail == null){
tail = new Node(e);
head = tail;
}else { // 链表不为空
// tail的next指向新节点
tail.next = new Node(e);
// 将tail移动到新节点位置
tail = tail.next;
}
size ++;
}
对于出队操作我们需要考虑三种情况：
- 链表为空，这种情况直接返回即可，不需要执行出队操作
- 链表中只有一个元素
- 链表中有多个元素
针对情况2、3我们需要先创建一个新的节点，指向head节点，然后将head节点指向它的下一个节点，再然后将新建的这个节点的next置为空使它脱离链表。对于链表中只有一个元素的情况，执行完上述操作后，还要将tail置为空，要不tail还会指向出队的节点。
出队：
public E dequeue(){
// 处理链表为空的情况
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
Node retNode = head;
head = head.next;
retNode.next = null;
// 处理链表中只有一个节点的情况
if(head == null)
tail = null;
size --;
return retNode.e;
}
使用链表实现队列的完整代码如下：
public class LinkedListQueue<E> implements Queue<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
// head记录头节点 tail记录尾节点
private Node head, tail;
// 记录链表中存储了多少元素
private int size;
public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
@Override
public void enqueue(E e){
// tail为空，说明链表为空
if(tail == null){
tail = new Node(e);
head = tail;
}else { // 链表不为空
// tail的next指向新节点
tail.next = new Node(e);
// 将tail移动到新节点位置
tail = tail.next;
}
size ++;
}
@Override
public E dequeue(){
// 处理链表为空的情况
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
Node retNode = head;
head = head.next;
retNode.next = null;
// 处理链表中只有一个节点的情况
if(head == null)
tail = null;
size --;
return retNode.e;
}
// 查看队首元素
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return head.e;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node cur = head;
while(cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
public static void main(String[] args){
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
# 链表真题练习
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
方法1：不使用虚拟头节点
class Solution {
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 null;
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;
}
}
方法2：使用虚拟头节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
}else {
prev = prev.next;
}
}
return dummyHead.next;
}
}
# 链表和递归
链表也是可以使用递归，因为链表本身就具备递归的性质，但是因为链表是一种线性结构，一般我们使用for循环就可以解决链表相关的问题。但是如果从链表就能深刻的打好递归的基础，可以为后面更深入的学习树这种结构打好基础。
递归本质上就是将原来的问题，转化为更小的同一个问题。
下面我们来举一个简单的例子：数组求和
对于数组求和我们可以将它转化如下
sum(arr[0, n-1]) = arr[0] + sum(arr[1, n-1]) // 转换为了一个更小的同一问题
sum(arr[1, n-1]) = arr[1] + sum(arr[2, n-1]) // 转换为了一个更小的同一问题
// 依次缩小到求一个元素的和
sum(arr[n-1, n-1]) = arr[n-1] + sum(arr[]) // 最后转化成了一个最基本的问题
对数组求和这个问题我们没有必要使用递归，但是使用递归的方式来实现数组求和这个问题是一个非常好的理解递归的开始，因为这个问题的逻辑非常简单，可以帮助我们更好的理解递归。
public class Sum {
// 用户只需要传入一个int型的数组即可
public static int sum(int[] arr) {
return sum(arr, 0);
}
// 计算arr[l...n)这个区间内所有数字的和
private static int sum(int[] arr, int l) {
if (l == arr.length) return 0;
return arr[l] + sum(arr, l + 1);
}
// 测试
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6};
System.out.println(sum(nums)); // 21
}
}
所有的递归算法都是可以分成两部分的，第一部分是求解这个最基本的问题，递归算法就是把原问题变成一个更小的问题，这个更小的问题可以变成更更小的问题，依次类推，直到原问题变成一个最基本的问题。在数组求和这个问题里if (l == arr.length)先判断下当前是不是一个最基本的问题，如果是的就返回0即可；第二部分是把原问题转化成更小的问题的过程。
我们在写递归函数的时候一定要注重递归函数的"宏观"语义，对于sum函数来说就是计算arr[l,n)这个范围里所有元素的和。递归函数本身就是一个函数，完成一个功能，它和一个函数a里调用一个函数b是没什么本质区别，只不过在递归函数里函数b的名字是a而已。在数组求和这个例子中sum函数里调用sum，我们可以把调用的这个sum"忘掉"，我们可以假象成我们现在有一个子逻辑叫sum，这个子逻辑需要传两个参数arr和l，它做的事情就是计算arr这个数组中[l, n)这个范围内所有元素的和。在这种情况下写一段逻辑怎么计算arr数组中从[l, n)这个范围数组的和，同时要用上sum这个函数？其实就是求arr[l] + sum(arr, l + 1)。
下图中的链表我们可以想象成0这个节点后面又挂了一个链表，对于链表来说我们可以把它理解成一个个节点的挂接，也可以理解成一个头接节点后面又挂载一个小的链表，依次类推，直到最后Null本身也可以当做一个链表。
下面我们用递归来解决上面删除链表中元素的问题：
对于最开始的链表我们可以理解成头节点就是e这个节点后面跟了一个更短的链表，假设现在我们有了一个函数这个函数可以递归删除这个小链表中所有值为val的节点，这样我们处理完这个小链表后，再判断头节点e的值是不是等于val，如果头节点的值不等于val，则将头节点和处理后的小链表拼接起来就得到了最终结果，如果头节点的值等于val，则这个处理后的小链表就是最终结果。
/// Leetcode 203. Remove Linked List Elements
/// https://leetcode.com/problems/remove-linked-list-elements/description/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 整个链表为空
if(head == null)
return head;
// 把removeElements这个函数想成一个子过程，它的作用就是删除一个链表中值为val的节点，也就是删除head后面的小链表中值为val的节点，所以第一个参数传入head.next，第二个参数传入要删除的值。res存的是head后面小链表删除值为val节点后的结果
ListNode res = removeElements(head.next, val);
// 判断head节点是否需要删除，如果head节点需要删除直接返回res
if(head.val == val)
return res;
else{
// 头节点不需要删除，则将头节点和小链表连接起来
head.next = res;
return head;
}
}
// 测试
public static void main(String[] args) {
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode res = (new Solution()).removeElements(head, 6);
System.out.println(res);
}
}
从图中可以看到head.next指向的就是处理后的小链表，如果head的值等于val，则直接返回head.next即可；如果head的值不等于val，则返回head即可，通过head就可以找到处理后的小链表。所以上述代码还可以简化如下：
class Solution5 {
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
// 测试
public static void main(String[] args) {
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode res = (new Solution5()).removeElements(head, 6);
System.out.println(res);
}
}
# 递归再深入
在前面介绍栈这种数据结构时，在介绍栈的应用时简单介绍了下程序调用的系统栈这种场景
递归和上面这张图是一样的，以数组求和这个类似为例，只不过是把fn1和fn2换成了sum而已。
下面我们来模拟下删除链表中值为val的的例子，至于数组求和的例子比较简单，大家可以自行模拟。
从链表 3 -> 4 -> 5 -> null 中删除值为4的节点
图片中代码前的1、2、3表示的是代码执行到第几步。
public ListNode removeElements(ListNode head, int val) {
if(head == null)
return head;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
开始执行代码，removeElements第一次调用：
执行第一步后，head的值是3，不等于空，开始执行第二步，head.next的值等于再调用一次removeElements的返回值，此时代码停到2等待第二次调用removeElements的结果；
第二次调用removeElements，这次调用我们将head.next也就是以4这个节点为头结点的链表传给了removeElements，来尝试删除这个新链表的元素。执行代码第一行，看现在的这个head是否为空，4不为空，开始执行第二个步，head.next的值等于第三次调用removeElements的返回值，此时代码停到2这个位置等待第三次调用removeElements的结果；
开始执行第三次调用removeElements函数，将head.next，也就是以5这个节点为头节点的链表传给removeElements，来尝试删除这个新链表的元素。执行代码第一行，看现在的这个head是否为空，5不为空，开始执行第二步，此时代码停到第二步等待第四次调用removeElements的结果；
第四次调用removeElements函数，将head.next，也就是以null这个节点为头节点的链表传给removeElements，来尝试删除这个新链表的元素。执行代码第一行，看现在的这个head是否为空，null为空，将null返回给第三次调用removeElements的2的位置使得head.next = null，执行第三步，head.next也就是null不等于val，直接返回5->null这个链表给第二次调用removeElements的head.next，执行第三步，此时head.val = 4等于val，返回head.next，也就是5->null这个链表给第一次调用removeElements的head.next，执行第三步，head.val也就是3不等于val，直接返回head，得到最终结果：3 -> 5 -> null这个链表。
递归调用是有代价的：
函数的调用是有时间开销的，包括记录当前代码执行到哪里，当前变量的状态等压入栈，还包括函数调用本身在计算机的底层要找个这个新的函数所在的位置，这些都是有一定的时间消耗的。
更重要的是递归调用是消耗系统栈的空间的，如果在递归调用中不处理最基本的那种情况也就是递归调用终止条件，递归调用就会一直进行下去，直到系统栈被沾满。
# 翻转链表
问题：
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 非递归实现 思路：
class Solution {
public ListNode reverseList(ListNode head) {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
- 递归实现 思路：
class Solution {
public ListNode reverseList(ListNode head) {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode node = reverseList(head.next)
head.next.next = head;
head.next = null;
}
}
← 队列