如何遞歸連接字符串元素列表

Question

我正在查看準備考試的示例，坦率地說，我對遞歸或列表，但特別是列表不是很好。

給出了一個節點類，它將保存字符串（不是泛型的）編寫一個名爲concat的遞歸java函數，它接受一個代表鏈表頭部的節點並返回一個表示鏈表中所有元素串聯的字符串如果列表爲空，則字符串應該也是。

任何幫助，將不勝感激。

（以下是我不得不類型之前，我問的問題:)

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

    } 

} 

感謝repsonses。

Answer 1

如果您的節點爲空，則返回一個空字符串。

否則，獲取字符串，進行遞歸調用（以獲得其餘節點的連接結果），並將其附加到字符串並返回結果。

Answer 2

因爲這聽起來像作業，我會提出建議。

首先寫入如果列表只有一個元素（即沒有下一個節點）將工作的方法。用它作爲遞歸調用的基礎。

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

在這種情況下，什麼是遞歸找到基本情況，以及如何將數據「分開」到這個基本情況。所以首先定義你的「基本情況」。

• 基本情況：函數參數爲空
• ，直到你得到的基本情況，追加節點的文本，並跳過的第一個元素

這是你的方法：

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：

public class Test { 
    // this is a very basic Node class 
    static class Node { 
     String text; 
     Node next; 

     public Node(String text) { 
      this.text = text; 
     } 
     // used for building the list 
     public Node add(String text) { 
      next = new Node(text); 
      return next; 
     } 
    } 

    // this is the recursive method concat 
    public static String concat(Node node) { 
     if (node == null) 
      return ""; 

     return node.text + " " + concat(node.next); 
    } 

    public static void main(String[] args) { 
     // build the list 
     Node head = new Node("hello"); 
     head.add("this").add("is").add("a").add("linked").add("list"); 

     // print the result of concat 
     System.out.println(concat(head)); 
    } 
} 

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