[30 points if in O(n), 25 points otherwise^[1]]

Add a new method reverse to the class LinkedList created in the problem 1. This method must reverse the order of the nodes in the list. For example, having applied reverse to the list [2 4 8 9 8], we will change it to [8 9 8 4 2].

Possible solution to the problem 1.

Use it only for your reference, do not copy it. Try to implement it yourself first! import java.util.NoSuchElementException;

public class LinkedList { private Node head; // first private Node tail; // last

private class Node { private int value; private Node next;

public Node(int value) { this.value = value;

} }

private boolean hasNext(Node node) { return (node.next != null);

}

private boolean isEmpty() { return (head == null);

}

public void print() {

Node current = head; System.out.print("[");

while (current != null) { if (hasNext(current)) {

System.out.print(current.value + ", ");

} else {

System.out.print(current.value);

} current = current.next;

}

System.out.println("]");

}

public void addFirst(int value) { Node node = new Node(value);

if (isEmpty()) { head = tail = node;

} else { node.next = head; head = node;

}

}

public void addLast(int value) { Node node = new Node(value); if (isEmpty()) { head = tail = node;

} else { tail.next = node; tail = node;

} }

public int indexOf(int value) { int index = 0; Node current = head;

while (current != null) { if (current.value == value) { return index;

} index++;

current = current.next;

}

return -1;

}

public boolean contains(int value) { return (indexOf(value) != -1);

}

public void deleteFirst() { if (isEmpty()) { throw new NoSuchElementException();

}

if (head == tail) { head = tail = null;

return;

}

Node formerHeadNext = head.next; head.next = null; head = formerHeadNext;

}

public Node previous(Node node) { if (isEmpty()) throw new NoSuchElementException();

Node current = head; while (current.next != node) { if (!hasNext(current)) { throw new NoSuchElementException();

} current = current.next;

} return current;

}

public void deleteLast() { if (isEmpty()) throw new NoSuchElementException();

if (head == tail) { head = tail = null;

return;

}

Node lastButOne = previous(tail); lastButOne.next = null; tail = lastButOne;

}

}