Please implement three methods in Java:

Method 1: reverse(Node) This method takes as its parameter a linked list, reverses the order of that list, and returns the node at the head of the reversed list. You may store temporary pointers to Nodes within the list (as in Node n = head), but do not create any new instances of Node; in other words, the expression new Node(...) should not appear anywhere in your implementation. Also, do not modify the value field inside each Node; your implementation should reverse the direction of the node pointers, not move values around.

Method 2: removeMaximumValues(Node, int) This method takes as parameters a linked list and an integer N and returns the linked list from which all instances of each of the N largest values in the input linked list have been removed. If the input value N is zero or negative, this method should simply return the list without modification. The other elements in the list should not be modified and their relative order must not be changed. Removing the N maximum values from an empty list should return the empty list for any value of N; an exception should not be thrown in this case, and in general you shouldnt throw exceptions unless we specify that you do so.

Because the values are Strings, you will need to use the String classs compareTo method to comp the Strings; see the Java API for help with that method. This method performs lexicographic comparison (similar to how dictionaries are sorted), so b is larger than a, and aa is larger than a, etc. Note that compareTo is undefined if its argument is null and will throw an exception in this case. Your implementation should not attempt to handle/catch that exception. We will not pass a list to your method that contains any nodes with null Strings.

For the same reason you should generally avoid get(int), we also suggest (but do not require), for the sake of efficiency, that you avoid using the provided remove(int) (i.e. remove an element by index) in your implementation of removeMaximumValues(int). A little repetitive code is preferable to code that is orders of magnitude slower.

Method 3: containsSubsequence(Node, Node) This method takes as input two lists, head and other, and determines whether the values stored in the list other are a subsequence of the values stored in the list head. A sequence T is a subsequence of S if T can be derived from S by deleting zero or more values from S without changing the relative ordering of the values. For example, the sequences [] (the empty sequence), [b], [a, c], and [a, b, c, d] are all subsequences of [a, b, c, d] (out of a total 16 possible subsequences). But [b, a] would not be a valid subsequence of [a, b, c, d] since ordering must be preserved. Note that the empty sequence is a subsequence of all possible sequences, therefore if other is the empty list, this method should return true. Also note that you should compare only the values stored in the two lists to determine if other is a subsequence of head. The nodes themselves do not need to be shared between the two lists, only the values stored in those nodes.

public class MyLinkedList {

static class Node {

String value;

Node next;

Node(String value, Node next) {

this.value = value;

this.next = next;

}

Node(String value) {

this(value, null);

}

}

protected Node head = null;

protected Node tail = null;

protected int size = 0;

public void addFirst(String value) {

Node newNode = new Node(value);

newNode.next = head;

head = newNode;

if (newNode.next == null) {

tail = newNode;

}

size++;

}

public void addLast(String value) {

Node newNode = new Node(value);

if (tail == null) {

head = newNode;

} else {

tail.next = newNode;

}

tail = newNode;

size++;

}

public void add(int index, String value) {

if (index < 0 || index > size)

throw new IndexOutOfBoundsException();

if (index == 0) {

addFirst(value);

} else if (index == size) {

addLast(value);

} else {

Node newNode = new Node(value);

Node current = head;

for (int i = 0; i < index - 1; i++) {

current = current.next;

}

if (current.next == null) {

tail = newNode;

}

newNode.next = current.next;

current.next = newNode;

size++;

}

}

public String get(int index) {

if (index < 0 || index >= size) {

throw new IndexOutOfBoundsException();

} else {

Node current = head;

for (int i = 0; i < index; i++) {

current = current.next;

}

return current.value;

}

}

public boolean contains(String value) {

Node current = head;

while (current != null) {

if (current.value == value || current.value != null && current.value.equals(value)) {

return true;

}

current = current.next;

}

return false;

}

public void removeFirst() {

if (head != null) {

head = head.next;

} else {

return;

}

if (head == null) {

tail = null;

}

if (size > 0)

size--;

}

public void removeLast() {

if (head == null) { // empty list

return;

} else if (head == tail) {

// single element list

head = null;

tail = null;

} else {

Node current = head;

while (current.next != tail) {

current = current.next;

}

tail = current;

current.next = null;

}

size--;

}

public void remove(int index) {

if (index < 0 || index >= size)

throw new IndexOutOfBoundsException();

else if (index == 0)

removeFirst();

else {

Node current = head;

for (int i = 0; i < index - 1; i++) {

current = current.next;

}

current.next = current.next.next;

if (current.next == null) {

tail = current;

}

size--;

}

}

/*

* Implement the methods below. Please do not change their signatures!

*/

public void reverse() {

/* IMPLEMENT THIS METHOD! */

}

public void removeMaximumValues(int N) {

/* IMPLEMENT THIS METHOD! */

}

public Boolean containsSubsequence(MyLinkedList two) {

/* IMPLEMENT THIS METHOD! */

return false;

}

}