206

這一題 - reverse linked list 算是經典中的經典啊，常常聽到，不過很久沒有寫也是有點忘記。我們手上有的是一個singly linked list，所以直覺上想起來，只要先產生一個vector，依序把ListNode存進這個vector，最後再從vector的最後一個element往前連，就可以得到反向的linked list了。

不過在實作過程中遭遇一個問題，感覺稍微碰觸到linked list比較不直覺的部分。就是假設我已經按照原本linked list存的順序，將每個ListNode存到vector裡，那接下來要怎麼樣init一個linked list，然後一個個把vector的element串成一個linked list?

不直覺的地方在於，我想直接把vector裡面的ListNode一個個串起來的時候，就會遭遇到自己指向自己的問題，這表示我對於linked list的操作上的直觀想法有問題:

C++ Code:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        vector<ListNode*> storage;
        ListNode* currentNode, reversedList;

        if(head == NULL || head->next == NULL)
            return head;

        currentNode = head;

        while(currentNode != NULL)
        {
            storage.push_back(currentNode);
            currentNode = currentNode->next;
        }

        /*不直覺的地方
        currentNode = storage[storage.size()-1];

        for(int i=storage.size()-1; i>=0; i--)
        {
            currentNode->next = storage[i];
            currentNode = currentNode->next;
        } 
        */
    }
};

重新來想一下應該怎麼寫，就會發現既然會蓋掉自己，那感覺就應該要有一個tmp的ListNode來存中間的產物，結果想了一下發現根本就不用那麼複雜，還在中間存出一個vector，直接在過程中反轉就好。假設以1 -> 2 -> 3 ->4這個例子來說，一開始head指向1。那只要在trace過程中紀錄關係即可，一開始先記錄prev = head (就是1)，next = prev->next (就是2)，就可以開始了。

1. tmp = next -> next (3)
2. next - > next = prev (2->1)
3. prev = next (2)
4. next = tmp (3)

寫出來的code在:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;

        ListNode* prev; 
        ListNode* next; 
        ListNode* tmp;

        prev = head;
        next = prev->next;

        while(next != NULL)
        {
            tmp = next->next;
            next->next = prev; //這一行是失敗的重點
            prev = next;
            next = tmp;
        }

        return prev;
    }
};

不過這份code還是有考慮得不夠的地方，每次跑起來都會超過時間限制，看起來是卡在while迴圈裡面，我用白癡debug方法，直接進while迴圈，分別在不同行後面加看看return prev，看是卡在哪一步，結果是卡在next->next = prev;這一行。

就是我反轉的時候，忘記把head->next設成NULL，一個比較好的寫法是，prev直接從NULL開始，就可以避免掉上面犯的錯誤:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;

        ListNode* prev; 
        ListNode* next; 
        ListNode* tmp;

        prev = NULL;
        next = head;

        while(next != NULL)
        {
            tmp = next->next;
            next->next = prev; 
            prev = next;
            next = tmp;
        }

        return prev;
    }
};

Java Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        /*
        Concept:
        1. create a new head 
        2. use a temp node to record head.next
        3. link head node to new head
        4. move new head to head
        */

        ListNode newHead = null;
        if(head == null || head.next == null) return head;
        ListNode node = head;
        while(node!=null){
            ListNode tmp = node.next;
            node.next = newHead;
            newHead = node;
            node = tmp;
        }
        return newHead;
    }
}

Recursive 解法

Steps:

 1. Divide the list in two parts - first node and rest of the linked list.
 2. Call reverse for the rest of the linked list.
 3. Link rest to first.
 4. Fix head pointer

C++ Code:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return head; // no node in the list

        ListNode* first = head;
        ListNode* rest = first->next;

        if(rest == NULL) return head; // only one node in the list

        /* reverse the rest list and put the first element at the end */
        rest = reverseList(rest);
        first->next->next = first;  

        /* tricky step -- see the diagram */
        first->next  = NULL;          

        /* fix the head pointer */
        return rest;
    }
};