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

img

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;
    }
};

results matching ""

    No results matching ""