再帰 - スレッド "main"の例外リンクリストの逆転中のjava.lang.StackOverflowError

Question

再帰を使用してリンクリストを逆転させるコードを記述しています。イムはこのエラーを受けて、なぜ理解できませんでしたか？いかなる援助も感謝します。

/** 
* Definition for singly-linked list. 
* class ListNode { 
*  public int val; 
*  public ListNode next; 
*  ListNode(int x) { val = x; next = null; } 
* } 
*/ 

public class Solution{ 
    public ListNode reverseList(ListNode a){ 
     if(a==null || a.next==null)return a;  
     ListNode ans=null; 
     ans = reverse(a,ans); 
     return ans; 
    } 
    private ListNode reverse(ListNode aa, ListNode ans){ 
     if(aa.next==null){ 
      ans = aa; 
      return ans; 
     } 
     ans = reverse(aa.next, ans); 
     ListNode temp = aa.next; 
     temp.next=aa; 
     aa.next=null; 
     return ans; 
    } 
} 

Answer 1

私はスニペット作成することによって、あなたのコードを実行している：私は、コードが正しく動作していると仮定し、この簡単なテストを実行することにより

public class Solution { 

    public static ListNode reverseList(ListNode a){ 
     if(a==null || a.next==null)return a; 
     ListNode ans=null; 
     ans = reverse(a,ans); 
     return ans; 
    } 

    private static ListNode reverse(ListNode aa, ListNode ans){ 
     if(aa.next==null){ 
      ans = aa; 
      return ans; 
     } 
     ans = reverse(aa.next, ans); 
     ListNode temp = aa.next; 
     temp.next=aa; 
     aa.next=null; 
     return ans; 
    } 

    public static class ListNode { 
     public int data;  // data stored in this node 
     public ListNode next; // link to next node in the list 

     // post: constructs a node with data 0 and null link 
     public ListNode() { 
      this(0, null); 
     } 

     // post: constructs a node with given data and null link 
     public ListNode(int data) { 
      this(data, null); 
     } 

     // post: constructs a node with given data and given link 
     public ListNode(int data, ListNode next) { 
      this.data = data; 
      this.next = next; 
     } 
    } 

    public static void main(String[] args) { 
     ListNode last = new ListNode(3); 
     ListNode middle = new ListNode(2, last); 
     ListNode first = new ListNode(1, middle); 

     ListNode listNode = reverseList(first); 

     System.out.println(listNode.data); 
     System.out.println(listNode.next.data); 
     System.out.println(listNode.next.next.data); 

    } 

} 

を。リンクされたリストがどのように動作しているかを視覚化する必要があります。なぜなら、リンクされたリストにサイクルがある可能性が高いからです。