The method for reversing a linked list is as below;
Reverse Method
public void reverseList() {
Node<E> curr = head;
Node<E> pre = null;
Node<E> incoming = null;
while(curr != null) {
incoming = curr.next; // store incoming item
curr.next = pre; // swap nodes
pre = curr; // increment also pre
curr = incoming; // increment current
}
head = pre; // pre is the latest item where
// curr is null
}
Three references are needed to reverse a list: pre, curr, incoming
... pre curr incoming
... --> (n-1) --> (n) --> (n+1) --> ...
To reverse a node, you have to store previous element, so that you can use the simple stament;
curr.next = pre;
To reverse the current element's direction. However, to iterate over the list, you have to store incoming element before the execution of the statement above because as reversing the current element's next reference, you don't know the incoming element anymore, that's why a third reference needed.
The demo code is as below;
LinkedList Sample Class
public class LinkedList<E> {
protected Node<E> head;
public LinkedList() {
head = null;
}
public LinkedList(E[] list) {
this();
addAll(list);
}
public void addAll(E[] list) {
for(int i = 0; i < list.length; i++)
add(list[i]);
}
public void add(E e) {
if(head == null)
head = new Node<E>(e);
else {
Node<E> temp = head;
while(temp.next != null)
temp = temp.next;
temp.next = new Node<E>(e);
}
}
public void reverseList() {
Node<E> curr = head;
Node<E> pre = null;
Node<E> incoming = null;
while(curr != null) {
incoming = curr.next; // store incoming item
curr.next = pre; // swap nodes
pre = curr; // increment also pre
curr = incoming; // increment current
}
head = pre; // pre is the latest item where
// curr is null
}
public void printList() {
Node<E> temp = head;
System.out.print("List: ");
while(temp != null) {
System.out.print(temp + " ");
temp = temp.next;
}
System.out.println();
}
public static class Node<E> {
protected E e;
protected Node<E> next;
public Node(E e) {
this.e = e;
this.next = null;
}
@Override
public String toString() {
return e.toString();
}
}
}
Test Code
public class ReverseLinkedList {
public static void main(String[] args) {
Integer[] list = { 4, 3, 2, 1 };
LinkedList<Integer> linkedList = new LinkedList<Integer>(list);
linkedList.printList();
linkedList.reverseList();
linkedList.printList();
}
}
Output
List: 4 3 2 1
List: 1 2 3 4