单链表递归倒序问题。

Question

public Node reverse(Node first)
{
    if(first == null) return null;
    if(first.next == null) return first;
    Node second = first.next;
    Node rest = reverse(second);
    second.next = first;
    first.next = null;
    return rest;
}

Node rest = reverse(second);这段之后具体是怎么执行的。
每次的rest的值是什么。是不是从链表最后一个往前返回rest值呢。。

感觉很奇怪。下面是鄙人拙计的想法。。
假如是 1→2→3这样的

    Node 2 = 1.next;
    Node rest = reverse(2);    
    2.next = 1;                                
    1.next = null;   
    //由下面的 reverse(2)中rest为3 还是返回3
    return rest;  

reverse(2);

↓
Node 3 = 2.next;
Node rest = reverse(3);
//由3.next==null→ return 3；
2.next = 1;

1.next = null;

return rest; → 3

总感觉我的理解有问题。。

请问下大家是哪里出问题了~~谢谢

Answer 1

写个测试程序验证一下就可以了：

public class TestLink {

static final class Node {

    final int value;

    Node next;

    public Node(int value) {
        super();
        this.value = value;
    }

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

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        String s = String.valueOf(value);
        if (next != null) {
            s += "-->" + next.toString();
        }
        return s;
    }

}

public static void main(String[] args) {
    int size=10;
    Node root = new Node(1);
    Node n = root;
    for (int i = 2; i <= size; i++) {
        Node m = new Node(i);
        n.next = m;
        n = m;
    }
    System.out.println(root);
    System.out.println(reverse(root));
}

public static Node reverse(Node first) {
    if (first == null)
        return null;
    if (first.next == null)
        return first;
    Node second = first.next;
    Node rest = reverse(second);
    second.next = first;
    first.next = null;
    return rest;
}

}

输出结果：
1-->2-->3-->4-->5-->6-->7-->8-->9-->10
10-->9-->8-->7-->6-->5-->4-->3-->2-->1
应该没问题