如何在Java中遞歸地複製鏈表的每個元素？

Question

我必須編寫一個重複的函數來複制鏈表的每個元素並返回一個鏈表，如果L = [2,3,4]，則重複（L）= [2,2,3,3,4 ，4]。我必須遞歸地做這件事。我意識到下面不是正確的解決方案，但我感到困惑。 =（

public class MyList { 
    int value; 
    MyList next; 

    public static MyList duplicate(MyList L){ 
     if(L.next == null){ 
      L.next.value = L.value; 
      L.next.next = null; 
     } else { 
      MyList temp = L.next; 
      L.next.value = L.value; 
      L.next.next = temp; 
      duplicate(L.next); 
     } 
     return L; 
    } 
} 

Answer 1

首先，檢查L不是空列表（null）。如果它包含一個值，返回具有重複兩次該值，然後通過複製列表的其餘部分的新列表。

通過給MyList構造，這是更具可讀性。

public class MyList { 
    int value; 
    MyList next; 

    public MyList(int value, MyList next) { 
     this.value = value; 
     this.next = next; 
    } 

    public static MyList duplicate(MyList list) { 
     if (list == null) { 
      return null; 
     } else { 
      return new MyList(list.value, 
        new MyList(list.value, 
         duplicate(list.next))); 
     } 
    } 
} 

Answer 2

您目前添加項目，然後呼叫遞歸，結束於不斷添加項目。

您可能需要在要素背後你遞歸的正向加工時，或遞歸後向後處理時。

---

讓我們創建一個向後的方向版本。我們首先遞歸地走到列表的末尾，然後向後解決遞歸，每次在之後添加項目。

public <E> void duplicateEntries(MyLinkedList<E> list) { 
    // Do nothing if list is empty 
    if (list.size() != 0) { 
     // Call the recursive method on the head node 
     duplicateEntriesHelper(list.head); 
    } 
} 

public <E> void duplicateEntriesHelper(Node<E> node) { 
    // Walk to the end of the list 
    if (node.next != null) { 
     duplicateEntriesHelper(node.next); 
    } 

    // Resolve recursion, duplicate current 
    // entry by inserting it after the current element 
    Node<E> duplicatedEntry = new Node<>(); 
    duplicatedEntry.data = node.data; 

    // Insert element after current node 
    duplicatedEntry.next = node.next; 
    node.next = duplicatedEntry; 
} 

---

的類我以前應該類似於：

public class MyLinkedList<E> { 
    public Node<E> head = null; 

    @Override 
    public String toString() { 
     // Build something like "MyLinkedList[2, 3, 4]" 
     StringBuilder sb = new StringBuilder(); 
     sb.append("MyLinkedList["); 

     StringJoiner sj = new StringJoiner(","); 
     Node<E> node = head; 
     while (node != null) { 
      sj.add(node); 
      node = node.next; 
     } 
     sb.append(sj); 

     sb.append("]"); 
     return sb.toString(); 
    } 
} 

public class Node<E> { 
    public Node next = null; 
    public E data = null; 

    @Override 
    public String toString() { 
     return E; 
    } 
} 

這裏是演示：

public static void main(String[] args) { 
    // Setup the list 
    MyLinkedList<Integer> list = new MyLinkedList<>(); 

    Node<Integer> first = new Node<>(); 
    first.data = 2; 
    Node<Integer> second = new Node<>(); 
    second.data = 3; 
    Node<Integer> third = new Node<>(); 
    third.data = 4; 

    list.head = data; 
    first.next = second; 
    second.next = third; 

    // Demonstrate the method 
    System.out.println("Before: " + list); 
    duplicateEntries(list); 
    System.out.println("After: " + list); 
} 

當然，你可以添加額外的方法和功能，它們。例如使用一些構造函數或getter/setter方法。