使用遞歸扭轉鏈表產生錯誤的輸出

Question

是不是有什麼毛病我扭轉了鏈表的遞歸方法？因爲我得到以下輸出只有1反轉後得到的印刷：

原始鏈表： 1 - > 2 - > 3 - > 4 - > 5 - >尾

反轉的LinkedList使用遞歸： 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

你不是從工作中很遠：

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

---

主要POI nts：

1. 根本不需要current，head是不可變的。
2. 您應該返回（和propegate）「新頭」，從最深的遞歸調用開始一路出了遞歸。

Answer 2

在ReverseRecursion， 你永遠不分配反轉的列表回到head。 更改此行：

ReverseRecursion(current.next); 

要這樣：

head = ReverseRecursion(current.next);