[7.11-7.13] Reverse a linked List

1. Implementation

One ->Two-> Three-> ø

One         

Two-> Three-> ø

            Two   

            Three-> ø

            Three-> two

 Three-> two-> one

// How do you reverse a linked list in place?


@Test
public void reverseLinkeDLsitTest()
{
    final LinkedList three= new LinkedList<>("3", null);
    final LinkedList two = new LinkedList<>("2", three)
    final LinkedLsit one = new LinkedList<>("1", two);


    final LinkedList reversed = LinkeDLsit.reverse(one);


    assertEquals("3", reversed.getElement() );
    assertEquals("2", reversed.getNext().getElement());
    assertEquals("1", reversed.getNExt().getNExt().getElement());
)

    
}


// #1 Iterative 


public void reverseLinkedList( ListNode head)
{

        // validate the output
        if ( head == null )
            return;
 

        ListNode p = head;
        ListNode q ;
        ListNode end = null;


        while ( p != null )
        {
             // tmp
             q = p.next;
              
             p.next = end;
             end = p;


             // assign tmp 
             p = q;
        }
}


// # 2 Recursive

public static  LinkedList reverse (final LinkedList ori)
{
      // validate the input
      if ( ori == null )
         throw new NullPointerException("cannot reverse a null list");
      
      // only one element
      if ( ori.getNext() == null )
          return ori;

      
      // Separate First   2->3->null == 2->null  3->nyll
      final LinkedList next = original.next;
      original.next = null;

     
      // Separate the Rest  3->null return
      final LinkedList otherReversed = reverse(next); // first return is only one element left

      // Rest -> First 3->null==> 3->2->null
      next.next = original;



      return otherReversed;
      


}


public class LinkedList {

     // Field
     private T value
     private LinkedList next;


     // constructor
     public LinkedList( T value, LinkedList<
T> next)      
     {
        this.value = value; 
        this.next = next;
     }


      public T getValue()
     {
        return value;
     }

     public LinkedList getNext()
     {
          return next;
     }
}