Reverse a Link List

 

 Program to Reverse a Link List

public class ReverseLinkList {

     public static Link reverse( Link head ) {
        Link last = null;
        Link p0 = head;
        Link p1 = p0 != null ? p0.next: null;
        Link p2 = p1 != null ? p1.next : null;
       
        return reverse( p0, p1, p2, last );
    }
   
    private static Link reverse( Link p0, Link p1, Link p2, Link last ) {
        if ( p0 == null ) return p0;
        if ( p1 == null ) {
            p0.next = last;
            return p0;
        }
        if ( p2 == null ) {
            p1.next = p0;
            p0.next = last;
            return p1;
        }
       
        // reverse middle, p2 can be null at this point
        p1.next = p0;
        p0.next = last;
       
        // reset pointers
        last = p1;
        p0 = p2;
        p1 = p0.next;
        p2 = p1 != null ? p1.next: null;
       
        return reverse( p0, p1, p2, last );   
       
    }

  public static Link build( int count) {
       
        if ( count == 0 ) return null;
        Link head = new Link( 1 );
        Link last = head;
        int a = 1;
        while ( count-- > 1 ) {
        Link link  = new Link( ++a );
        last.next = link;
        last = link;
        }
        return head;
    }
   
    public static void print( Link head ) {
        if ( head == null ) return;
        int count = 1;
    Link k = head;
        do {
            System.out.println( count++ + "::"+ k.name());
            k = k.next;
        }while( k != null );
    }

public static void main( String[] args ) {
        Link head = build(10);
        print( head );
        Link reverseHead = reverse( head );
        System.out.println("Reversing");
        print( reverseHead );
    }


}

class Link {
    private String name;
    Link next;
   
    Link( int name, Link next ) {
        this.name = name + "";
        this.next = next;
    }
   
    Link ( int name ) {
        this( name, null );
    }
   
    String name() {
        return this.name;
    }
   
}