206. Reverse Linked List

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution: Iteratively:

Use preDummy trick and head will be the tail after reversing. Iteratively insert tail.next to the beginning of the list until tail.next equals null. 

   public ListNode reverseList(ListNode head) {  
     if(head==null || head.next==null) return head;  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=head;  
     ListNode tail=head;  
     while(tail.next!=null){  
       ListNode cur=tail.next;  
       tail.next=cur.next;  
       cur.next=preDummy.next;  
       preDummy.next=cur;  
     }  
     return preDummy.next;      
   }  

Recursively:
Eg. 1 -> 2 -> 3 ->4
if we reverse 2->3->4 ->null will give us 4->3->2->null with 1->2->null and then we set 1.next.next =1 then 1.next=null which makes list like 4->3-> 2->1->null, then return 4.
So we can recursively solve this problem by reverse the head.next node as new head node and insert  the current head node to the tail position.
The base case is if the current head is null or head.next==null we can simply return head.

  public ListNode reverseList(ListNode head) {  
    if(head==null || head.next==null) return head;  
    ListNode cur=reverseList(head.next);  
    head.next.next=head;  
    head.next=null;  
     return cur;  
   }