リンクされたリストの要素を再帰で追加する方法はありますか？

Question

私は、要素を再帰的に追加する必要があるが、機能していない "add"という非公開の再帰的メソッドを作成しました。私はjavaが参照渡しを持っていないことを知っているので、どのように再帰的に要素を追加するでしょうか？私が間違っている場所を教えてくれれば幸いです。ありがとう

public class linkedIt2 { 
private int length = 0; 
private Node head; 


private class Node { 
    Node next; 
    int data; 
    public Node(int data, Node next) { 
     this.data = data; 
     this.next = next; 
    } 

    public Node(int data) { 
     this.data = data; 
     this.next = null; 
    } 
} 


public linkedIt2() { 
    head = null; 
} 

private void add(Node cur, int data) { 
    if (cur != null) { 
     add(cur.next, data); 
    } else { 
     cur = new Node(data, null); 
    } 
} 

public linkedIt2 insert(int data) { 
    add(this.head, data); 
    length++; 
    return this; 
} 
} 

Answer 1

問題は、参照を変更することはできません。参照が値によって呼び出されるため、cur.nextは決して変更されません。再帰呼び出しの前にcur.nextを変更する必要があります。

「値による呼び出し」というJavaの概念を理解する必要があります。参照による呼び出しはありません。参照は値として転送されるため、参照パラメータ自体を変更してください。最初に使用されたオブジェクトには何も起こりません。 おそらく： http://javadude.com/articles/passbyvalue.htm はそれをより明確にします。

一つの解決策：あなたのに似て：

最初あなたはcurがnullでないことを確認する必要があります。関数内でcur.nextにアクセスすることができます。 nullの場合は再帰を終了し、そうでない場合は再帰を終了します。

private void add(Node cur, int data) { 
    if (cur.next != null) { 
    add(cur.next, data);  
    } else { 
    cur.next = new Node(data, null); 
    } 
} 

public linkedIt2 insert(int data) { 
    if (this.head == null) { 
    this.head = new Node(data, null); 
    } else { 
    add(this.head, data); 
    } 
    length++; 
    return this; 
} 

またはノードに再帰を行い、それ自体を操作させます。他の解決策の状態として。それはさらに良いです。ここ

Answer 2

あなたの間違いは、あなたがこれを呼び出すと、それは実際にあなたがしてメソッドを呼び出し、変数を更新することはありません新しいノードを指すように、ローカル変数CURを更新

cur = new Node(data, null); 

ラインであります。単純な例に

public static void setToFive(int num) { 
    num = 5; 
    System.out.println(num); //Always prints 5 
} 

public static void test() { 
    int test = 3; 
    setToFive(test); 
    System.out.println(test); //Still prints 3 since only num was updated, not test 
} 

を与えるためにそれでは単にhead.add（データ）を呼び出すと、あなたの長カウンタをインクリメント再帰的にあなたが

private class Node { 
    //... 
    public void add(int data) { 
     if (next == null) { 
      next = new Node(data, null); 
     } else { 
      next.add(data); 
     } 
} 

ような何かを行うことができ、元の問題に戻り、要素を追加します。

新しいノードを作成するとき、メソッドの中に含まれる変数ではなく、クラスのインスタンス変数をポイントするように設定されているので、このバージョンがうまく機能します。