文字列要素のリストを再帰的に連結する方法

Question

私は試験の準備をしている例を見ていますが、率直に言って再帰やリスト、特にリストではあまりよくありません。

ノードクラスが与えられていると、文字列（汎用ではない）が保持され、連結リストの先頭を表すノードをとり、リストのすべての要素の連結を表す文字列を返すconcatという再帰的なJava関数を記述します。リストが空であれば、文字列も同じでなければなりません。

ご協力いただければ幸いです。

（以下は、私が質問:) repsonsesため

public static String FindConcat(Node head) { 
    String s = ""; 
    if(head == null) return s; 
    else if(head.next = null) { 
     s += head.data; 
     return s; 
    } 
    else { 

    } 

} 

感謝を尋ねた前に、私はタイプを持っていたものです。

Answer 1

ノードがnullの場合は、空の文字列を返します。

それ以外の場合は、文字列を取得し、再帰呼び出しを行い（残りのノードの連結結果を取得する）、文字列に追加して結果を返します。

Answer 2

宿題のように聞こえるので、私は提案をします。

リストが1つの要素しか持たない場合（つまり、次のノードがない場合）に動作するメソッドを記述することから始めます。あなたの再帰呼び出しの基礎としてそれを使用してください。

Answer 3

リンクされたリストの再帰的なトラバーサルは、リストの末尾にあるかどうかを確認するように見えます（参照はnullでした）。そうでない場合は、次の要素に対して再帰呼び出しを行いますあなたがそうであれば、ベースケースのことをやってください。ノードは外部から次のようになりと仮定すると：

public class Node{ 
    public Node getNext(); 
    public String toString(); 
} 

...あなたの方法は、（あなたが外にこれを実行するために使用しているクラス内で）次のようになります。

public String concatList(Node head){ 
    if(head == null){ 
     return ""; //empty list is a null pointer: return empty string 
    } 
    return head.toString() + concatList(head.getNext()); 
} 

最後のリスト、または全くリストがない場合は、同じように見えます - 指定された空の文字列を返します。それ以外のものはすべて現在のノードを取り出し、文字列の残りの部分の連結バージョンを取得して作成したリストに連結します。

注意：何かがあなたのリストを壊して実際にループである場合、これはチェックされず、Javaがこの再帰関数のループ最適化を正しく検出しない限り、スタックメモリがなくなるまで永遠に実行されます。単に永遠に走る。

Answer 4

このケースでは、どのような再帰が基本ケースを見つけるのか、この基本ケースにデータを「分ける」方法です。だから最初にあなたの "ベースケース"を定義します。

• ベースケース：あなたは

を、基本ケースを取得するノードのテキストを追加し、最初の要素をスキップティル関数の引数は

nullです。これは、あなたの方法であって、

public static String FindConcat(Node head) { 
    if (head == null) 
     return ""; // base case 

    // devide it down (run recursive FindConcat on the _next_ node) 
    return head.data + FindConcat(head.next); 
} 

この単純な例では、印刷されますhello this is a linked list：

ここでは3210

Answer 5

は非常に完全な例です：

import java.util.Arrays; 
import java.util.List; 
import java.util.UUID; 

public class RecurisveLinkedListExample 
{ 
    public static String concat(final Node node) 
    { 
     if (node == null) 
     { 
      return ""; 
     } 
     else 
     { 
      return node.getData() + concat(node.getNext()); 
     } 
    } 

    public static void main(String[] args) 
    { 
     final List<String> input = Arrays.asList("A", "B", "C", "D"); 
     final Node head = new Node(null, input.get(0)); 
     Node previous = head; 
     for (int i = 1; i < input.size(); i++) 
     { 
      previous = previous.addNext(input.get(i)); 
     } 

     System.out.println(concat(head)); 
    } 

    public static class Node 
    { 
     private final UUID id; 
     private final Node previous; 
     private final String data; 
     private Node next; 

     public Node(final Node previous, final String data) 
     { 
      this.previous = previous; 
      this.data = data; 
      this.next = null; 
      this.id = UUID.randomUUID(); 
     } 

     public Node getPrevious() 
     { 
      return previous; 
     } 

     public String getData() 
     { 
      return data; 
     } 

     public Node addNext(final String data) 
     { 
      this.next = new Node(this, data); 
      return this.next; 
     } 

     public Node getNext() 
     { 
      return next; 
     } 

     @Override 
     public String toString() 
     { 
      return String.format("%s:%s:%s", 
        this.previous == null ? "HEAD" : this.previous.id, 
        this.data, 
        this.next == null ? "TAIL" : this.next.id); 
     } 
    } 
}