LinkedListの最小数と加算関数の作成

Question

ロジックを試して、少なくとも1つのリストを引数として取る関数の再帰的バージョンであるminとadditionMerge関数を書き込もうとしています（最初のノードリストの）。これは、LinkedListクラスのメンバー関数であるラッパー関数によって呼び出されるプライベートヘルパー関数です。

public class LinkedList { 

    private static class ListNode { 

     public int firstItem; 
     public ListNode restOfList; 
    } 
    private ListNode first; 

    /** 
    * Create an empty list. 
    */ 

    public LinkedList() { 
     first = null; 
    } 


     public LinkedList(int n) { 
    first = countDown(n); 
} 

public LinkedList(String s) { 
    String[] temp = s.split(","); 
    for (int i = temp.length-1; i >= 0; i--) { 
     first = insertAtFront(first, Integer.parseInt(temp[i])); 
    } 
} 

public int length() { 
    return length(first); 
} 

private static int length(ListNode list) { 
    if (list == null) { 
     return 0; 
    } 
    int temp = length(list.restOfList); 
    return temp + 1; 
} 

public boolean contains(int value) { 
    return contains(first, value); 
} 

private static boolean contains(ListNode list, int value) { 
    if (list == null) { 
     return false; 
    } 
    if (list.firstItem == value) { 
     return true; 
    } 
    return contains(list.restOfList, value); 

} 

public int sum() { 
    return sum(first); 
} 

private static int sum(ListNode list) { 
    if (list == null) { 
     return 0; 
    } 
    return sum(list.restOfList) + list.firstItem; 
} 

public int count(int target) { 
    return count(first, target); 
} 

private static int count(ListNode list, int target) { 
    if (list == null) { 
     return 0; 
    } 
    int temp = count(list.restOfList, target); 
    if (list.firstItem == target) { 
     temp++; 
    } 
    return temp; 
} 

public void replace(int oldValue, int newValue) { 
    replace(first, oldValue, newValue); 
} 

private static void replace(ListNode list, int oldValue, int newValue) { 
    if (list == null) { 
     return; 
    } 
    replace(list.restOfList, oldValue, newValue); 
    if (list.firstItem == oldValue) { 
     list.firstItem = newValue; 
    } 
    } 

    public void insertAtFront(int n) { 
     first = insertAtFront(first, n); 
    } 

    private static ListNode insertAtFront(ListNode list, int n) { 
    ListNode answer = new ListNode(); 
    answer.firstItem = n; 
    answer.restOfList = list; 
    return answer; 
    } 

    private static ListNode countDown(int n) { 
    if (n == 1) { 
     ListNode answer = new ListNode(); 
     answer.firstItem = 1; 
     answer.restOfList = null; 
     return answer; 
    } 
    ListNode temp = countDown(n - 1); 
    ListNode answer = insertAtFront(temp, n); 
    return answer; 
    } 

    public void insertAtBack(int item) { 
    first = insertAtBack(first, item); 
    } 

    private static ListNode insertAtBack(ListNode list, int item) { 
    if (list == null) { 
     ListNode answer = new ListNode(); 
     answer.firstItem = item; 
     answer.restOfList = null; 
     return answer; 
    } 
    //List answer = new ListNode(); 
    //answer.firstItem = list.firstItem; 
    ListNode temp = insertAtBack(list.restOfList, item); 
    //answer.restOfList = temp; 
    list.restOfList = temp; 
    return list; 
    } 

    public void concatenate(LinkedList otherList) { 
    this.first = concatenate(this.first, otherList.first); 
    } 

    private static ListNode concatenate(ListNode list1, ListNode list2) { 
    if (list1 == null) { 
     return list2; 
    } 
    ListNode temp = concatenate(list1.restOfList, list2); 
    list1.restOfList = temp; 
    return list1; 
    } 

    public void filter(int item) { 
    first = filter(first, item); 
    } 

@Override 
    public String toString() { 
    if (first == null) { 
     return ""; 
    } 
    StringBuilder sb = new StringBuilder(256); 
    sb.append(first.firstItem); 
    for (ListNode current = first.restOfList; 
      current != null; 
      current = current.restOfList) { 
     sb.append(','); 
     sb.append(current.firstItem); 
    } 
    return sb.toString(); 
    } 

    private static ListNode filter(ListNode list, int item) { 
    if (list == null) { 
     return null; 
    } 
    ListNode temp = filter(list.restOfList, item); 
    if (list.firstItem == item) { 
     return temp; 
    } 
    list.restOfList = temp; 
    return list; 
} 



    public int min() throws RuntimeException { 

     if (first == null) 
     throw new RuntimeException("List is Empty"); 
     else 
      return min(); 

     } 




    // * A private recursive helper function that returns the minimum item in a 
    * list whose first node is the argument list. 


private static int min(ListNode list) throws RuntimeException { 
    if (list == null) { 
     return 0; 


     } 


    } 


    public void additionMerge(LinkedList l2) { 



} 


* Every node in the list that begins with node 
* node1 is increased by the ammount of the corresponding 
* node in the list that begins with node node2. 
* If one list is longer than the other, the missing nodes 
* in the shorter list are assumed to be 0. 

    private static ListNode additionMerge(ListNode node1, ListNode node2) { 
      if (list == null) { 
      return null; 
      } 


     } 

} 

Answer 1

これは宿題でない場合は、私のアドバイスは、次のとおりです。

• 独自のLinkedListクラスを記述しないでください。既存のoutを使用し、追加の機能をヘルパークラスとして追加するか、既存のクラスを拡張して追加します。

• 独自のリンクリストクラスを実装する場合は、再帰を使用する必要があります。再帰はきちんとしたsoltionを与えますが、Javaの再帰で大きな欠点があります。 JVMはテールコールの最適化を行いません。したがって、深く再帰的に繰り返す（例えば、長いリストを再帰的にトラバースする）反復的なアルゴリズムは、StackOverflowErrorを引き起こす可能性があります。