创建链表的最小数量和加法函数

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类。 使用现有的 out，并将额外的功能添加为帮助程序类或通过扩展现有类。

• 如果你决定实现你自己的链表类，那么你应该注意使用递归。 递归给出了一个简洁的解决方案，但是在Java中递归有一个主要的缺点。 JVM不做尾部调用优化，因此深度递归的回避算法(例如递归遍历长列表(很容易导致StackOverflowError。