A LinkedList is reversed using 3 pointers: the previous element, the current element and the next element.
The current element next value is saved in the next variable. The current node next value is set to the previous value. The current Node is save in the previous variable. Then the next value is saved in the current one. The process is run on all the elements of the linkedlist. The previous pointer will contain the last element in the process. It is returned as the Head of the reverted linkedlist.
public class InterviewLinkedListReverse {
static class Node {
int value;
Node next;
Node(int i){
this.value = i;
}
}
public Node reverse(Node head) {
Node previous = null;
Node current = head;
Node next;
while( current != null ){
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
public void show(Node head) {
while( head != null ){
System.out.println( + head.value );
head = head.next;
}
}
public static void main(String[] argv) throws Exception {
InterviewLinkedListReverse t = new InterviewLinkedListReverse();
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
// Show the current linked list
System.out.println( "Current Linked List" );
t.show(head);
System.out.println();
// Reverse the linked list
Node reversed = t.reverse( head );
// Show the reversed linked list
System.out.println( "Reversed Linked List" );
t.show(reversed);
}
}
Current Linked List 1 2 3 Reversed Linked List 3 2 1
This example reverse the LinkedList in O of N with N being the number of Elements in the list and in O of 1 as no more memory is needed. The linked list can also be reversed using a stack: all the elements are added to the stack. Then the reversed List is created by removing the elements from the stack. Using the stack removes the need to keep the pointers, all the elements are added to the stack, then removed from the stack. The last element added to the stack is the first one out, so we just need to relink the elements to have the list reverted.