链表和递归

从一道leetcode题目开始

题目描述：

avatar

看一下题目内容其实很简单就是删除一个链表中值为val的所有节点并且返回被删除完的链表。

上篇文章讲了如何进行链表操作，这时候我们其实就可以通过老方法遍历整个链表，然后通过比较每个节点的值和val的值是否相等，相等则删除，不相等则保留。

示例代码：

  class Solution {
      //这里的ListNode是leetcode给定的，里面包含next和val字段
  public ListNode removeElements(ListNode head, int val) {
    //创建一个虚拟头结点
    ListNode virtualNode=new ListNode(0);
    //虚拟头结点的next节点是头结点
    virtualNode.next=head;
    //将虚拟头结点赋值给currentNode当前节点
    ListNode currentNode=virtualNode;
    while (currentNode.next!=null){
        //通过遍历当前节点来删除元素
      if (currentNode.next.val==val){
        //如果当前头结点的next元素的val值等于给定的val
        //则将当前节点的next元素直接指向next的next
        //那么原来next节点就直接被删除了
        currentNode.next=currentNode.next.next;
      }else {
        //如果不相等则跳到下一个节点，循环知道currentNode的next节点为null
        currentNode=currentNode.next;
      }
    }
    //返回虚拟头结点的next，这里就是被删除元素的原来的头结点
    return virtualNode.next;
  }
}

递归

avatar

在考虑递归如何写的时候我们先需要了解递归的宏观语意。

一个递归函数其实本质就是函数调用，只不过它是自己调用自己。

递归函数就是将原来的问题转化为更小的问题，知道最后求出最基本的解。

最基本的解一般是我们通过if条件判断来终结的，如果不添加if判断给递归函数一个终结（最基本的解，例如求阶乘的时候等于1等于0的时候就是最基本的解），那么计算机就会无限产生递归调用，这会导致cpu的方法栈（写栈的时候提过，函数调用就是通过栈来实现的）爆满从而报错。

avatar

如何写一个递归函数，我们不要去考虑它的实现细节，最好是通过宏观语意来完成它。

首先我们最能确定的就是它的最基本解，然后我们需要在原本函数里面再次调用该函数并修改参数（目的是将原问题转换为更小的问题）。上图的代码只是最简单的示例，当递归函数稍微再复杂点的时候，我们就需要获取到递归调用函数产生的值并对这个return的值来做些修改最后再返回给上一级调用这个级别的递归函数的函数。

使用递归来实现链表的删除(上述题目)

首先完成一个递归函数我们需要先确定我们怎么把这个递归函数变为更小的函数。

这里，我们将这个删除长度n的链表中元素的问题转换成先判断从第二个节点开始到最后节点中删除符合条件的节点，然后再转换为从第三个节点到最后节点删除符合条件的节点，直到我们的问题变成了删除最后一个空节点中符合条件的元素，当然这个时候空节点里面是不可能有的，所以我们这时候直接返回head，这样最基本解就出来了。

1
2
3

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

之后就是转换为更小的问题了。

//将问题转换为小问题
ListNode result=removeElements(head.next,val);
//每次return都是return给上一级递归的结果
//如果当前节点的val值和给定val相等
//则直接return给上一级不包含该节点的链表
if(head.val==val){
    return result;
}else{
    //如果不相等说明不需要删除
    //则需要将返回的结果前面加上头结点head在返回head
    head.next=result;
    return head;
}

完整代码：

 public  ListNode removeElements(ListNode head,int val){
 //首先考虑最基本的问题
 if (head==null){
   return null;
 }
 ListNode resultNode=removeElements(head.next,val);
 if (head.val==val){
   return resultNode;
 }else {
  head.next=resultNode;
  return head;
 }
}

其实整个问题可以这么理解，我需要删除一个链表中符合元素的节点，那么我把这个问题转化为小问题，将整个链表转换为从2开始到结尾的链表，然后S到从3开始到结尾的链表，最后到从结尾到结尾的节点（null），那么我就是从最后一个节点找需要删除的节点，假设如果最后一个节点是要删除的节点，那么这时候我们只需要将这个节点删除并且返回给上一级调用递归函数。这时候我们返回的null然后上一级接收到的result就是null，然后这个函数继续执行到if(head.val==val)，这时候就判断（第二级递归就是最后两个节点的链表）当前链表中的头结点的val是否满足，满足就跟刚刚一样“删除”该节点，不满足就将这个head的next设置为result，也就是将result的头结点暂时设置为当前head（将当前head设置为头结点并返回给上一级调用的函数），这样无限的返回，最后返回的就是原本链表中需要删除元素后的链表了。

这个时候我们可以将递归写的更简单

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

简单实用递归实现链表的创建

首先我们考虑如何通过递归实现该功能，创建一个链表，我们将问题缩小就是从创建节点开始。例如我们现在给定一个数组，然后我们通过这个数组来创建链表。首先这个数组的索引肯定是我们递归实现的条件，比如一个10个元素的数组，我们需要创建十个元素的链表，我们可以将问题变为创建从索引1开始到结束的链表，然后从索引2到结束，最后到从末尾到末尾（创建最后一个元素），所以这时候我们最基本条件就出来了。

1
2
3

if((index+1)==array.length){
  return null;
}

这个时候我们就要来实现将问题转换为小问题
其实很简单。

ListNode result=createElement(array,index+1);
ListNode currentNode=new ListNode(array[index]);
currentNode.next=result;
return currentNode;

完整代码：

public static ListNode createListNode(int[] array,int index){
  if ((index+1)==array.length){
    return new ListNode(array[index]);
  }else {
    ListNode result=createListNode(array,index+1);
    ListNode currentNode=new ListNode(array[index]);
    currentNode.next=result;
    return currentNode;
  }
}

杂谈

这个星期开始复习的信号系统，对于我这个学物联网的同学，不会什么高数，硬件是真的很烦躁，信号考完了，能不能过就靠老师助攻了。今天写篇博客来缓解一下一个星期没写代码的愧疚，这个递归还真的有点难理解，还需要勤敲勤练。加油吧！！