leetcode第一刷_Submission Details

有段時間沒更新了，專心刷了幾天，差十幾道結束，決定把第一季更完，然後按照我的理解分類再分析一遍，第二遍的時候應該會按照問題分類，應該會引用第一季的，如果想到或找到更好的解法，會更新第一季。

鏈表的問題就是惡心，思路大多直接，對指針的操作要非常小心。我自己常犯的錯誤主要有：

1. 在取val或者取next時，沒有判空，造成Runtime Error。

2. 空指針和只有一個節點之類的邊界情況。

3. 更新鏈表之後，沒有將鏈表尾部置空，造成它指向其他的節點，構成環，或者想拆下鏈表的一部分時沒有把那部分的尾部置空，構成環。

4. 同時用到多個指針時，平移，更新指針供下一個循環使用時，指針的更新順序弄錯了，造成了空指針或者環，出現TLE或者RE。

這道題還有點意思，第一個節點後面接的是最後一個，第二個接倒數第二個，我一開始看錯題了，以為是從一半開始，第一個接第n/2個呢。不過思路差不多，這道題只要先找到一半的位置，把後面那部分鏈表反轉一下，就可以同時用一個頭指針和一個一半位置的指針更新了。

鏈表的O(N)和固定控件反轉是解決很多鏈表問題的工具，而且很容易寫錯，應該多寫幾遍。我的寫法很好理解，用三個指針。

下面是ac代碼：

ListNode *reverse(ListNode *head){
    if(!head || !head->next)
        return head;
    ListNode *one = head, *two = head->next, *three = head->next->next;
    one->next = NULL;
    while(three){
        two->next = one;
        one = two;
        two = three;
        three = three->next;
    }
    two->next = one;
    return two;
}

class Solution {
public:
    void reorderList(ListNode *head) {
        if(!head || !head->next)
            return;
        int len=0;
        ListNode *pNode = head, *rpNode = head, *pre = NULL;
        while(pNode){
            len++;
            pNode = pNode->next;
        }
        if(len == 2)
            return;
        len = (len+1)/2;
        for(int i=0;inext;
        }
        if(pre)
            pre->next = NULL;
        rpNode = reverse(rpNode);
        ListNode *test = rpNode;
        pNode = head;
        while(rpNode){
            pre = rpNode->next;
            rpNode->next = pNode->next;
            pNode->next = rpNode;
            pNode = pNode->next->next;
            rpNode = pre;
        }
        return;
    }
};