Basically there are two methods of reversing a linked list – iterative and recursive. Lets discuss the iterative method :
Logic: Iterate trough the linked list. In loop, change next to prev, prev to current and current to next.
This is simple and has the following complexity :
Time Complexity: O(n)
Space Complexity: O(1)
<pre><code>private static void reverseIterative() { Node prev=null; Node current= head; Node next=null; while(current != null) { next = current.next; current.next = prev; prev = current; current = next; } head = prev; }</code></pre>
here is the code for both forward and reverse manner.
public class LinkedListUtils { LinkedListNode head; class LinkedListNode { Object data; LinkedListNode next; public LinkedListNode( Object data, LinkedListNode next ) { this.data = data; this.next = next; } } public void addFirst( Object data ) { head = new LinkedListNode( data, head ); } /** * Prints the linked-list by traversing it forwards. */ public static void print( LinkedListNode node ) { if( node != null ) { // print till it doesnt find null values. System.out.print( node.data + " " ); // print 15 first then node.next and so on. print( node.next ); // instead of node=node.next and cursor = head directly fun. call can also be used } // called without using temporary node(resursion..) // this can also be used , but for understanding using this method here recursion example of function // for( LinkedListNode cursor = node; cursor != null; cursor = cursor.next ) { // System.out.print(cursor.data +" " ); // } } /** * Prints the linked-list by traversing it backwards (in reverse). */ public static void printReverse( LinkedListNode node ) { if( node != null ) { printReverse( node.next ); // node = node.next System.out.print( node.data + " " ); } } /** * Test Method */ public static void main( String[ ] args ) { // Initialize and populate the linked-list LinkedListUtils list = new LinkedListUtils( ); for( int i = 0; i < 16; i++ ) { list.addFirst( i ); } // Print the linked-list forwards System.out.println( "Forwards: " ); LinkedListUtils.print( list.head ); // Print the linked-list backwards (in reverse) System.out.println( "\nBackwards: " ); LinkedListUtils.printReverse( list.head ); } }