java - Java中递归地反转链表

Question

我正在尝试实现反向链接列表。新的列表必须递归创建。

我正在反向列表中创建第一个节点，并且尝试创建一个子列表 Next，其中下一个元素为 next.next，最后将此子列表分配为该节点的下一个。问题是下一个节点仍然是 NIL，尽管我在 for 循环中重新创建了它。

编辑: 该函数不得更改(添加参数)，因为某些测试正在其上运行。

class Node {
    private Object item;
    private Node next,current;

    public Node(Object o, Node n) {
        this.item = o;
        this.next = n;
    } 

    public Node(Node n) {
    }

    public static final Node NIL = new Node(Node.NIL, Node.NIL);

    public Object getItem() {
        return this.item;
    }

    public Node getNext() {
        return this.next;
    }

    public void setItem(Object o) {
        this.item = o;
    }

    public void setNext(Node n) {
        this.next = n;
    }

    // this method returns the item with index number i
    public Object nthItem(int i) {
        Node p = this;
        while (p!=null){
            for (int k=1;k<=i;k++){
                p=p.next; 
            }
            return p.item;
        }
        return null;  
    }

    // this method returns the the next item of the node
    public Node nthNext(int i) {
        Node p = this;
        while (p!=null){
            for (int k=1;k<=i;k++){
                p=p.next; 
            }
            return p.getNext();
        }
        return null;
    }

    public Node nthNode(int i) {
        Node p = this;
        while (p!=null){
            for (int k=1;k<=i;k++){
                p=p.next; 
            }
            return p;
        }
        return NIL;  
    }

    public int length(){
        if (this == NIL) return 0;
        else return 1 + next.length();
    }

    public Node remove(Object o){
        Node p = this;
        if (p == NIL) return NIL;
        else if(p.item == o) {
            p = p.next;
            return p.remove(o);
        } 
        else return new Node(p.item, p.next.remove(o)); 
    }

    public Node reverse() {
        int i = this.length()-1;
        if(this == NIL) return NIL;

        Node node = new Node(Node.NIL, Node.NIL);

        Node next = NIL;

        //create the first node in the reversed list
        if(i >= 1) node = new Node(nthItem(i), next);
        else node = new Node(nthItem(i), Node.NIL);

        //iterate through the original list and create a next node
        if (i>0) {
            for (int k=i; k>=0; k--){
                if (k<=0)  {
                    next = NIL;
                }
                else {
                    next = new Node(nthItem(k-1),next);
                }               
            }
        }

        //debugging in console
        System.out.println("final node = " + next.item+" ");
        return node;
    }
}

class Test{

    public static void main(String[] string){
        Node n = new Node(1, Node.NIL);
        Node nn = new Node(2, n);

        Node r = nn.reverse();

        System.out.println("\t item " + r.getItem()+ " " + r.getNext().getItem() + " length " + r.length());
    }
}

Answer 1

这是一道题，旨在测试你是否理解隐式堆栈。 每次进行递归调用时，都会添加一个堆栈帧，因此将堆栈视为迭代执行例程。

反转列表:

1. 按顺序堆叠所有元素
2. 通过弹出每个元素来创建一个新列表。

现在将其转换为递归调用

//in [1,2,3,null]
Node reverse(Node n){

    //base case
    if(n == null)
    {
        return null;
    }

    // returns [null,3,2,1]
    Node next = reverse(n.getNext());
    next.setNext(n);// set the next nodes next to its previous(n on unwinding)
    return n;
}

请注意，这里的反向方法不会返回新的头，要获取反向列表的头，请执行以下操作，也许可以将上面的a作为辅助器。

Node oldHead = n;
Node newHead = tail(n);
oldHead.reverse();