VietMX Staff asked 3 years ago
Nothing faster than O(n) can be done. You need to traverse the list and alter pointers on every node, so time will be proportional to the number of elements.
Implementation
public void reverse(Node head) {
Node curr = head, prev = null;
while (head.next != null) {
head = head.next; // move the head to next node
curr.next = prev; // break the link to the next node and assign it to previous
prev = curr; // we are done with previous, move it to next node
curr = head; // current moves along with head
}
head.next = prev; //for last node
}