# 35 Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

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

題目解說:

這題是要反轉linked list ，可以用遞迴或雙指針解決。若用指針的話，有個關鍵點，就是head是原來的linked list，把pre = head; 之後，pre跟head一樣都指到同個物件，

假設linked list 1→2→3→4→null，

而

物件 1 記憶體位址 0x100 ，物件1的next指向 物件2 也是指向 0x020 ;

物件 2 記憶體位址 0x020 ，物件2的next指向 物件3 也是指向 0x311 ;

物件 3 記憶體位址 0x311 ，物件3的next指向 物件4 也是指向 0x520 ;

物件 4 記憶體位址 0x520 ，物件4的next指向 NULL ;

head 指向物件1 Ox100;

next = head.next; 表示next是指向 "物件1的next指向 物件2" 也就是指向 0x020

temp = null 表示temp指向null

pre = head 表示pre是指向 "物件1" 也就是指向 0x100

pre.next = null 表示指向 "物件1的next指向 null"，注意這裡修改物件1的next指向，所以此時有參考到物件1的都會受影嚮，如:此時的head，此時的head.next就是指向null

這裡要pre.next = null 用意是搞出1→null,

程式碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
       // ListNode pre = head;
       //  ListNode next = head.next;
       //  ListNode temp = null;
       //  pre.next = null;
       //  while(next!= null){
       //      temp = next.next;
       //      next.next = pre;
       //      pre = next;
       //      next = temp;
       //  }
       //  return pre;
        
        
        
        //step 1 find nextNode
        ListNode pre = head;
        ListNode next = head.next;
        ListNode temp = null;
        pre.next = null;
        // ListNode node = ;
         //print 
            temp = head;
        System.out.println("head ListNode");
            while(temp != null){
                System.out.print( temp.val + " , ");
                temp = temp.next;
            }
            System.out.println("\n"); 
        System.out.println("start pre = " + pre  + " , head = " + head + ", pre.next = " + pre.next + " , head.next = " + head.next);
        while(next != null ){
            temp = next.next;
            if(next.next != null){
                 System.out.println("next.next = " + next.next + " ,next.next.val = "+next.next.val +" , head.next = " + head.next );
            }
            // else{
                 // System.out.println("next.next = " + next.next + " ,next.next.val = "+next.next.val +" , head.next = " + head.next );
            // }
           
            next.next = pre;
             System.out.println("before pre = " + pre + " ,pre.val = "+pre.val);
            pre = next;
             System.out.println("now pre = " + pre  + " , head = " + head + " , next = " + next + " , temp = " + temp);
            System.out.println("after pre = " + pre + " ,pre.val = "+pre.val);
            next = temp;
        }
           //print 
            temp = pre;
        System.out.println("pre ListNode");
            while(temp != null){
                System.out.print( temp.val + " , ");
                temp = temp.next;
            }
            System.out.println("\n");
        
         //print 
            temp = head;
        System.out.println("head ListNode");
            while(temp != null){
                System.out.print( temp.val + " , ");
                temp = temp.next;
            }
            System.out.println("\n");
            
        return pre;
    }
}

另一個解法是遞迴

這解法是反過來，就是假設linked list 1→2→3→4→5→null，

第一次會代入 (1， 2) ，再代入 (2， 3)、 再代入 (3， 4)、再代入 (4， 5)、再代入 (5， null)，此時

進入if條件

回轉node ，此時node 指定 5物件。 5→null

這時沒有指定物件5的next指向哪裡。

__________________________________

回轉node，把5物件的next指向4物件，並把4物件指向null 5→4→null

__________________________________

回轉node，把4物件的next指向3物件，並把3物件指向null 5→4→3→null

__________________________________

回轉node，把3物件的next指向2物件，並把2物件指向null 5→4→3→2→null

__________________________________

回轉node，把2物件的next指向1物件，並把1物件指向null 5→4→3→2→1→null

__________________________________

回到main裡的return node，5→4→3→2→1→null，

程式碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
       // ListNode pre = head;
       //  ListNode next = head.next;
       //  ListNode temp = null;
       //  pre.next = null;
       //  while(next!= null){
       //      temp = next.next;
       //      next.next = pre;
       //      pre = next;
       //      next = temp;
       //  }
        // return pre;
        
        return helper(head,head.next);
        // return head;
    } 
    
    public ListNode helper(ListNode node1, ListNode node2) {
        if(node2 == null) {
            //print node1
            ListNode t = node1;
            while(t != null){
                 System.out.println("ent , t = " + t + " , t.val = " + t.val);
                t = t.next;
            }
            return node1;
        } 
        if(node2 != null && node2.next != null){
             System.out.println("enter helper , node2 = " + node2 + " , node2.val = " + node2.val + " , node2.next = " + node2.next  + " , node2.next.val = " + node2.next.val);
        }else{
            if(node2 != null){
                 System.out.println("enter helper , node2 = " + node2 + " , node2.val = " + node2.val );
            }
        }
        
        
        ListNode node = helper(node2, node2.next);
        System.out.println("node = " + node + " , node.val = " + node.val);
        node2.next = node1;
         System.out.println("now node2 = " + node2 + " , node2.val = " + node2.val+ " , node2.next = " + node2.next + " , node2.next.val = " + node2.next.val);
        node1.next = null;
        if(node1 != null && node1.next != null){
             System.out.println("now node1 = " + node1 + " , node1.val = " + node1.val + " , node1.next = " + node1.next + " , node1.next.val = " + node1.next.val);
        }
       
        return node;
    }
}
/*
輸出結果:
enter helper , node2 = ListNode@d716361 , node2.val = 2 , node2.next = ListNode@6ff3c5b5 , node2.next.val = 3
enter helper , node2 = ListNode@6ff3c5b5 , node2.val = 3 , node2.next = ListNode@3764951d , node2.next.val = 4
enter helper , node2 = ListNode@3764951d , node2.val = 4 , node2.next = ListNode@4b1210ee , node2.next.val = 5
enter helper , node2 = ListNode@4b1210ee , node2.val = 5
ent , t = ListNode@4b1210ee , t.val = 5
node = ListNode@4b1210ee , node.val = 5
now node2 = ListNode@4b1210ee , node2.val = 5 , node2.next = ListNode@3764951d , node2.next.val = 4
node = ListNode@4b1210ee , node.val = 5
now node2 = ListNode@3764951d , node2.val = 4 , node2.next = ListNode@6ff3c5b5 , node2.next.val = 3
node = ListNode@4b1210ee , node.val = 5
now node2 = ListNode@6ff3c5b5 , node2.val = 3 , node2.next = ListNode@d716361 , node2.next.val = 2
node = ListNode@4b1210ee , node.val = 5
now node2 = ListNode@d716361 , node2.val = 2 , node2.next = ListNode@4d7e1886 , node2.next.val = 1
*/