//CODE

public class HasPrefixSumProblem {

public static class Node {

private E data;

private Node next;

public Node(E data, Node next) {

this.data = data;

this.next = next;

}

public Node(E data) {

this(data, null);

}

public void setData(E data) {

this.data = data;

}

public void setNext(Node next) {

this.next = next;

}

public E getData() {

return data;

}

public Node getNext() {

return next;

}

}

/**

* TODO EXERCISE 5:

* Implement a method that determines if a Linked List

* has an initial sequence of nodes whose values sum to n.

*

* If so, it returns an integer corresponding to how many elements at the

* beginning of the list add up to n.

*

* The method receives as parameter a Node that represents the head node of a Singly Linked List,

* as well as a integer n denoting a target sum to search for.

*

* It is assumed that the list always has at least one node.

*

* If no sequence of initial elements adds up to n, the method will

* return a negative value, which is specified as follows.

* 1. The negative of the size of the list if the sum

* of all elements in the list is less than n.

* 2. The negative of the minimum number of elements at the

* beginning of the list whose sum exceeds n.

*

* Examples:

* 1) {1,2,3,4,5}, n = 10 -> returns 4

* 2) {2,4,6,8,10}, n = 10 -> returns -3 (since 2 + 4 + 6 = 12, which is larger than n = 10)

* 3) {1,2,3,4}, n = 15 -> returns -4 (since 1 + 2 + 3 + 4 = 10, which is smaller than n = 15)

*

* All the elements in the list are assumed to be non-negative integers.

*

* @param first - Head Node of Singly Linked List

* @param n - Integer denoting target sum

* @return Number of elements needed to sum up to n

*/

public int hasPrefixSum(Node first, int n) {

/*TODO ADD YOUR CODE HERE*/

return -Integer.MAX_VALUE; // Dummy Return

}

}

3. (20 pts) Head over to CircularDoublyLinkedList. java after finishing exercise 2. The instructions for this exercise are as follows: - A circulardoublylinkedList is a linked list where every node has a next pointer and a previous pointer. What is going to differentiate this from a regular DoublyLinkedList is that the header and trailer point to each other, making the references at the end of the List circle back to the beginning of the list. - Given the base code, create an implementation of the CirculardoublyLinkedList class (with dummy header and trailer) with the knowledge obtained from lectures and previous lab exercises. - Implementations that do not have ALL member methods implemented will receive at most 50% of the credit obtained upon inspection from the professor and/or TAs