java - 创建LinkedList的最小数和加法函数

Question

我在尝试逻辑并尝试编写 min 和 additionMerge 函数及其函数的递归版本时遇到问题，该函数至少将一个列表作为参数(列表的第一个节点)。这将是一个私有(private)辅助函数，由作为 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 不进行尾调用优化，因此深度递归的递归算法(例如递归遍历长列表)容易导致 StackOverflowError。