創建LinkedList的最小數量和加法函數

Question

我在嘗試邏輯時試圖編寫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類。使用現有的，並添加額外的功能作爲助手類或擴展現有的類。

• 如果你決定實現你自己的鏈表類，那麼你應該小心使用遞歸。遞歸提供了一個簡潔的解決方案，但是在Java中遞歸有一個主要缺點。 JVM不會執行尾部調用優化，因此深度遞歸（例如，遞歸遍歷長列表）的recusive算法容易導致StackOverflowError。