Interview Questions

Java Program to Reverse a Linked List

Use the following code to reverse a Linked list using Java.

/**
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

public class LinkedList {

        static Element root;

        /**
         * Program main method starts here
         *
         * @param args
         */

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                root = new Element(1, null);
                root.setNext(new Element(2, null));
                Element next = root.getNext();
                next.setNext(new Element(3, null));
                Element next1 = next.getNext();
                next1.setNext(new Element(4, null));
                System.out.println("Linked List : ");
                printLst(root);
                System.out.println();
                System.out.println("Reversed List : ");
                revLnkLst(root);
        }

        public static void printLst(Element root) {
                Element e1 = root;
                System.out.print(e1.data + "->");
                while (e1.next != null) {
                        e1 = e1.next;
                        System.out.print(e1.data + "->");
                }
        }

        /*
         * This method reverses the linked list given the head node.
         */

        public static void revLnkLst(Element e1) {

                Element currNode = e1;
                Element nextNode = e1.next;
                Element loopNode = new Element(0, null);
                currNode.next = null;

                while (loopNode != null) {
                        loopNode = nextNode.next;
                        nextNode.next = currNode;
                        currNode = nextNode;
                        nextNode = loopNode;
                }

                printLst(currNode);
        }
}

/*
 * A simple data structure to represent a linked list with data and next fields.
 */

class Element {
        Element next; // represents the next element in the list
        int data;

        public Element(int data, Element nt) {
                this.next = nt;
                this.data = data;
        }

        public Element getNext() {
                return next;
        }

        public void setNext(Element next) {
                this.next = next;
        }

        public int getData() {
                return data;
        }

        public void setData(int data) {
                this.data = data;
        }
}

Output:

Linked List :
1->2->3->4->
Reversed List :
4->3->2->1->