没有返回值的add递归，老师帮忙看看是否正确？

public void add(LinkedListR listR, int index, E e) {

if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index"); }
if (index == 0) {
listR.head=new Node(e,listR.head);
} else {
Node removed = listR.head;
listR.head=listR.head.next;
add(listR, index - 1, e);
removed.next = listR.head;
listR.head=removed;
}
size++;
}

飞飞侠91 2022-07-19

源自：动态数据结构基础：链表 2-9 链表添加元素递归方法的常见问题解析

收起

1回答

liuyubobobo 2022-07-21 03:40:58

是有问题的。

下面的代码的 add 使用了你的逻辑。测试的 main 函数中，你会看到，当最后一个添加操作在 index = 2 的位置添加了 666 以后，原来的链表 index = 2 位置后面的部分丢失了。

即：0->1->2->3->4->null 在 index = 2 添加 666 以后，应该是：

0->1->666->2->3->4->null

你的逻辑的得到结果是：

0->1->666->null

另外，你的程序中的 size 也会多次添加，在同样的这份程序中，一共添加了 6 个元素，你的程序最终得到的 size 是 18。

可以自己仔细调试一下，理解一下，为什么会这样？

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 void add(LinkedList<E> listR, int index, E e){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");
        if(index == 0)
            listR.head = new Node(e);
        else{
            Node removed = listR.head;
            listR.head=listR.head.next;
            add(listR, index - 1, e);
            removed.next = listR.head;
            listR.head=removed;
        }
        size ++;
    }
    
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        for(Node cur = head ; cur != null ; cur = cur.next)
            res.append(cur + "->");
        res.append("NULL");
        return res.toString();
    }
    
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for(int i = 0 ; i < 5 ; i ++){
            linkedList.add(linkedList, i, i);
            System.out.println(linkedList);
        }
        linkedList.add(linkedList, 2, 666);
        System.out.println(linkedList); // 这个输出是错的
        
        System.out.println(linkedList.size); // 这个输出也是错的
    }
}

继续加油！：）

收起回答

提问者飞飞侠91 #1

老师您好，1、第34行应该是listR.head=new Node(e,listR.head);
2、size++不能放在递归函数内，好像放到递归函数哪里都不行，只能够另外使用函数调用递归函数，然后再size++；
谢谢老师！

2022-07-21 21:58:42
liuyubobobo 回复提问者飞飞侠91 #2

第一个问题是我“转移”你的代码的时候出的错误，抱歉。
第二个问题，size 只要跟着 new 就好。因为 new 一个新的 Node 的时候，才是真正的添加一个节点的时候。所以这个代码是正确的：

```
public void add(LinkedList<E> listR, int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
if(index == 0){
listR.head = new Node(e, listR.head);
size ++;
}
else{
Node removed = listR.head;
listR.head=listR.head.next;
add(listR, index - 1, e);
removed.next = listR.head;
listR.head=removed;
}
}
```

不过这样只是逻辑正确了，在我看来这个函数接口设计的怪怪的。在调用添加一个元素的时候，需要：linkedList.add(linkedList, 2, 666); 本身就是对 linkedList 做调用，第一个参数还要把 linkedList 传进去。可以思考一下能不能不这样做？当然，如果只是追求逻辑正确，到这里就可以了。相信通过这个练习，你对递归的理解更深刻了：）

继续加油！：）

2022-07-21 23:43:24