Reverse a Linked List

This can be achieved either iteratively or recursively.

Iterative

1. We consider 3 nodes at the time, namely a current node, a node that comes before it and a node that comes after it.
2. We currently have a link between from previous->current->next.  We alter pointers in such a way that current points to previous (previous<-current).  
3. We then reset the pointers current and previous to point to their respective next nodes
4. We repeat till current is null (we've reached the end of the list.
5. Once we're done resetting all the pointers, previous will point to the last element.  We set this as the new head of the list.

      public Node<Type> reverse(Node<Type> head)  
      {  
           Node<Type> current=head;  
           Node<Type> previous=null,next=null;  
           while(current!=null)  
           {  
                next=current.next;  
                current.next=previous;  
                previous=current;  
                current=next;  
           }  
           head=previous;  
           return head;  
      }  

This runs in O(N) because we go through the entire list once while doing the reversal.

Recursive

1. In the recursive solution, we basically traverse till the end of the list.
2. Once we've reached the last element, we can set this as the new head.
3. For all the rest of the recursive iterations, we now have to reset two links.  We have to make current point to previous and break the link between previous and current.

      public void reverseRecurse(Node<Type> current)  
      {  
           if(current==null )  
                return;  
           if(current.next==null)  
           {  
                this.head=current;  
                return;  
           }  
           reverseRecurse(current.next);  
           current.next.next=current;  
           current.next=null;  
      }  

This implementation requires O(n) because it has to go through the entire list once, but also requires O(n) space in terms of the stack frames used for the recursion.

Complete Implementation

 public class LinkedListReverse<Type> {  
      private Node<Type> head;  
      public static class Node<Type> {  
           Type data;  
           Node<Type> next;  
           public Node(Type data) {  
                this.data = data;  
                this.next = null;  
           }  
      }  
      public LinkedListReverse() {  
           head = null;  
      }  
      public void push(Type item) {  
           Node<Type> newNode = new Node<Type>(item);  
           newNode.next = head;  
           head = newNode;  
      }  
      public void print(Node<Type> head) {  
           while (head != null) {  
                System.out.print(head.data + ",");  
                head = head.next;  
           }  
           System.out.println();  
      }  
      public Node<Type> reverse(Node<Type> head) {  
           Node<Type> current = head;  
           Node<Type> previous = null, next = null;  
           while (current != null) {  
                next = current.next;  
                current.next = previous;  
                previous = current;  
                current = next;  
           }  
           head = previous;  
           return head;  
      }  
      public void reverseRecurse(Node<Type> current) {  
           if (current == null)  
                return;  
           if (current.next == null) {  
                this.head = current;  
                return;  
           }  
           reverseRecurse(current.next);  
           current.next.next = current;  
           current.next = null;  
      }  
      public static void main(String args[]) {  
           LinkedListReverse<Integer> list = new LinkedListReverse<Integer>();  
           list.push(1);  
           list.push(2);  
           list.push(3);  
           list.push(4);  
           list.push(5);  
           list.print(list.head);  
           list.head = list.reverse(list.head);  
           list.print(list.head);  
           list.reverseRecurse(list.head);  
           list.print(list.head);  
      }  
 }  

Sample Output

5,4,3,2,1,

1,2,3,4,5,

5,4,3,2,1,