关于使用递归实现链表的增删操作

Question

递归思想：基本和老师您在课程中说讲的思想一致。
并且我这里的代码是不使用虚拟头节点的代码
1.这下面是我自己写的增操作的代码，这里我有一个小疑问：

public void add(int index, E e){

        if(index < 0 && index > size)
            throw new IllegalArgumentException("index is illegal");

        this.head = add(index, e, this.head);
        size ++;
    }

    public Node add(int index, E e, Node head){

        if(index == 0){
            head = new Node(e, head);
        }
        else{
            Node res = add(index - 1, e, head.next);
            head.next = res;
        }

        return head;
    }

在第一个add中，为什么add(index, e, this.head)前面必须要有this.head呢？事实上我去掉这个this.head之后，增加元素时链表会一直是NULL，并且最后还会报NullPointer的异常。而我在问答区搜索了一下，看了别人的解答，却不需要添加这样的代码，以下是我搜索到的代码：

public void add(E e, int index) {
    if (index < 0 || index > size) {
      throw new IllegalArgumentException("LinkedList.add failed, index is illegal!");
    }
    Node<E> previous = dummyHead;
    addWithRecursiton(e, previous, 0, index);
    size++;
  }
 
  /**
   * 
   * @param e  待添加的元素
   * @param previous 指定插入索引的前一节点
   * @param current 当前递归索引
   * @param index 指定添加索引
   */
  private void addWithRecursiton(E e, Node<E> previous, int current, int index){
    if (current == index){
      previous.next = new Node(e, previous.next);
      return;
    }
    addWithRecursiton(e, previous.next, current + 1, index);
  }

2.这下面是我自己写的删除操作的代码：

public void remove(int index){

        if(index < 0 && index >= size)
            throw new IllegalArgumentException("the index is illegal");

        this.head = remove(index, this.head);
        size --;
    }

    public Node remove(int index, Node head){

        if(index == 0){
            Node delNode = head;
            head = delNode.next;
            delNode.next = null;
        }
        else{
            Node res = remove(index - 1, head.next);
            head.next = res;
        }
        return head;
    }
这里的代码有一个比较大的问题，就是按我这种返回Node型变量的递归函数做的话我无法保存删除节点的元素值，请问该怎么修改代码以解决这个问题呢？

Answer 1

liuyubobobo 2018-12-01 02:16:38

1

对于为什么要有this.head = add(index, e, this.head); 其中的原因，和课程中介绍的递归删除算法（5-3至5-5），我们的remove要返回节点，道理是一样的。设想，如果没有return，你的添加逻辑只在递归终止操作的head = new Node(e, head);这句话中。而head只是这个函数中的一个局部变量（引用）而已。当这个函数执行完毕，这个局部变量就被释放了，而他所指向的空间也就丢失了。而return回去，让他赋值给上一层的head.next，才可以真正的吧这个new出来的节点挂接在整个链表表上。

关于一个head和head.next的不同，也可以参考这个问答：http://coding.imooc.com/learn/questiondetail/88146.html

至于你给出的第二段添加逻辑代码，就是因为传进去的引用参数是待插入节点的前一个节点（由于使用虚拟头结点）。所以，相应的添加新节点的代码是：previous.next = new Node(e, previous.next); 这使得新的节点被直接添加到了整个链表中：）

2

remove使用递归的方式删除，保留删除值确实会比较麻烦。这是因为Java天生不支持多个返回值。如果能返回多个值，这个问题就解决了。所以，只能绕个弯子，使用List的方式返回多个值。当然，在这里，我们只需要返回两个值，使用Pair也是可以的。我在课程的补充代码中，提供了基于返回Pair的remove递归删除算法，可以参考。传送门：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/05-Recursion/Optional-01-Recursive-LinkedList/src/LinkedListR.java

加油！：）

• 提问者 martin123_ #1

  多亏老师的回答，我知道自己在哪里产生误解了，其实就是没搞懂head和head.next的区别，感谢老师的解答！