Reverse Link List

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 );
 }
}

 

Advertisements