1 2 3 4 |
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. |
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