使用递归反转链表生成错误的输出

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

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

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;
}

见repl

要点：

你根本不需要 current，head 是不可变的。
你应该return（并传播）"New Head"，从最深的递归调用开始一直到递归。

使用递归反转链表生成错误的输出

reversing the linkedlist using recursion generating wrong output

java

linked-list