使用递归反转linkedlist会生成错误的输出

Question

我反转链表的递归方法有问题吗？因为我得到了以下输出，只有1在反转后打印出来：

原始链接列表：1->2-->3-->4-->5-->尾部

使用递归的反向链表：1-->尾部

public class ReverseList {
    public static List ReverseRecursion(List head){

        List current = head;
        if(current == null){
            return null;
        }
        if(current.next == null){
            head = current;
            return head;
        }
        ReverseRecursion(current.next);
        current.next.next = current;
        current.next = null;
        return head;
    }

    public static void main (String[] args){
    // Created a Single LinkedList
    List myList = new List(1);
    myList.next = new List(2);
    myList.next.next = new List(3);
    myList.next.next.next = new List(4);
    myList.next.next.next.next = new List(5);
    System.out.println("Original LinkedList: n"+myList.toString());

    System.out.println("Reversed LinkedList Using Recursion: n"+ReverseRecursion(myList));
    }
}
class List {
    int value;
    List next;
    public List(int k){
        value = k;
        next = null;
    }
    public String toString(){
        List cur = this;
        String output = "";
        while(cur != null){
            output+=cur.value+"-->";
            cur = cur.next;
        }
        return output+"Tail";

    }
}

Answer 1

在CCD_ 1中，您永远不会将反向列表分配回CCD_ 2。更改此行：

ReverseRecursion(current.next);

对此：

head = ReverseRecursion(current.next);

Answer 2

您离工作代码不远了：

public static List ReverseRecursion(List head){
    List newHead;
    if(head == null){
        return null;
    }
    if(head.next == null){
        return head;
    }
    newHead = ReverseRecursion(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

参见回复

---

要点：

1. 您根本不需要current，head是不可变的
2. 您应该返回（并推进）"New Head"，从最深的递归调用开始，一直到递归结束