Reverse a Linked List

Objective:
Reverse a linked list.  For example, resulting list after reversing the following list will have nodes in this order -  3, 2, 1.

To reverse a linked list, we need to maintain three pointers prev, current and next. Initially, prev will be pointing to null. We need to traverse through the list and move each pointer one node at a time. In each iteration, we need to unlink current.next from next and point to prev. We need to keep in mind that we need to move next first, so that we don't loose track of next node due to this unlinking. At the end, head will point to the last node in the chain and that way we'll reverse the whole linked list. This algorithm can implemented in iterative as well as recursive fashion.

Following java code gives solution for both the approaches:

Iterative Program:

public class LinkedList {

    Node head;
    Node lastNode;

    public static class Node {
        int data;
        Node next;

        public Node(int data){
            this.data = data;
            this.next = null;
        }
    }

    public void appendNode(int data){

        Node node = new Node(data);

        if(head == null){
            head = node;
            lastNode = head;
        }else {
            lastNode.next = node;
            lastNode = node;
        }
    }

    public void printList(){
        Node temp = head;
        while(temp != null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}

public class ReverseLinkedList {

    private static LinkedList reverseList(LinkedList list) {
        LinkedList.Node prev = null;
        LinkedList.Node temp = list.head;

        while (temp != null) {
            LinkedList.Node current = temp;
            LinkedList.Node next = current.next;
            current.next = prev;
            temp = next;
            prev = current;
        }
        list.head = prev;

        return list;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.appendNode(1);
        list.appendNode(2);
        list.appendNode(3);
        list.appendNode(18);
        list.appendNode(4);
        list.printList();

        LinkedList reverseList = reverseList(list);
        System.out.println();

        list.printList();
    }
}

Recursive Program:

public class ReverseLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.appendNode(1);
        list.appendNode(2);
        list.appendNode(3);
        list.appendNode(18);
        list.appendNode(4);
        list.printList();

        LinkedList.Node newHead = recursiveReverse(list.head, null);
        list.head = newHead;
        System.out.println();

        list.printList();
    }


    private static LinkedList.Node recursiveReverse(LinkedList.Node head, 

                                                                LinkedList.Node prev) {
        if(head == null){
            return prev;
        }
        LinkedList.Node tmp = head.next;
        head.next = prev;
        return recursiveReverse(tmp, head);
    }
}