How to reverse Singly Linked List?

Program: How to reverse Singly Linked List?

Description:

Write a sample code to reverse Singly Linked List by iterating through it only once.

Recursive Method:

1) Divide the list in two parts - first node and rest of the linked list. 2) Call reverse for the rest of the linked list. 3) Link rest to first. 4) Fix head pointer.

Code:

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 package com.java2novice.ds.linkedlist;    public class SinglyLinkedListImpl<T> {        private Node<T> head;            public void add(T element){                    Node<T> nd = new Node<T>();         nd.setValue(element);         System.out.println("Adding: "+element);         Node<T> tmp = head;         while(true){             if(tmp == null){                 //since there is only one element, both head and                 //tail points to the same object.                 head = nd;                 break;             } else if(tmp.getNextRef() == null){                 tmp.setNextRef(nd);                 break;             } else {                 tmp = tmp.getNextRef();             }         }     }            public void traverse(){                    Node<T> tmp = head;         while(true){             if(tmp == null){                 break;             }             System.out.print(tmp.getValue()+"\t");             tmp = tmp.getNextRef();         }     }           public void reverse(){                   System.out.println("\nreversing the linked list\n");         Node<T> prev = null;         Node<T> current = head;         Node<T> next = null;         while(current != null){             next = current.getNextRef();             current.setNextRef(prev);             prev = current;             current = next;         }         head = prev;     }           public static void main(String a[]){         SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<Integer>();         sl.add(3);         sl.add(32);         sl.add(54);         sl.add(89);         System.out.println();         sl.traverse();         System.out.println();         sl.reverse();         sl.traverse();     } }    class Node<T> implements Comparable<T> {            private T value;     private Node<T> nextRef;            public T getValue() {         return value;     }     public void setValue(T value) {         this.value = value;     }     public Node<T> getNextRef() {         return nextRef;     }     public void setNextRef(Node<T> ref) {         this.nextRef = ref;     }     @Override     public int compareTo(T arg) {         if(arg == this.value){             return 0;         } else {             return 1;         }     } }

Output:

Adding: 3 Adding: 32 Adding: 54 Adding: 89 3 32 54 89 reversing the linked list 89 54 32 3

- See more at: http://www.java2novice.com/java-interview-programs/revese-singly-linked-list/#sthash.wLLhBX8C.dpuf