237 刪除鏈表中的節(jié)點

剛開始讀題有點迷惑，怎么就只給了一個node，又不是單鏈表，無法獲取node的前驅(qū)，刪除了node鏈表不就斷了么。后來想到辦法，先把node的后繼的值復(fù)制到node中，然后node指向后繼的后繼，最后把node原來的后繼刪掉。還是挺巧妙的題目。
代碼：

time: 97.68%, memory: 5.39%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode *n = node -> next;
        node -> val = n -> val;
        node -> next = n -> next;
        delete n;
    }
};

19 刪除鏈表的倒數(shù)第n個節(jié)點

標(biāo)簽：雙指針，鏈表
第一種解法是兩次掃描的做法，為的是熟悉一下鏈表的操作。

leetcode的鏈表中，head指的就是第一個元素，不是哨兵節(jié)點，最后也沒有尾哨兵節(jié)點，所以必要的時候，可以手動添加哨兵節(jié)點來方便操作，當(dāng)然輸出的時候別忘了刪掉。

這里添加一個頭哨兵節(jié)點，是為了處理第一個節(jié)點被刪的情況。

time: 100%, memory: 16.65%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int cnt = 0;
        ListNode* pre = new ListNode(0), *cur = head; 
        pre -> next = head;  // 設(shè)置哨兵
        for(; cur != NULL; cur = cur -> next){
            cnt++;
        }
        int idx = cnt - n;
        cur = pre;
        while(idx--){
            cur = cur -> next;
        }
        ListNode* tmp = cur -> next;
        cur -> next = tmp -> next;
        delete tmp;
        return pre -> next;
    }
};

第二種做法是只掃描一遍的，設(shè)置兩個指針，保持兩個指針的距離始終為n，當(dāng)右邊的指針到達(dá)末尾時，左邊的指針就到了要刪除節(jié)點的前驅(qū)。
代碼：

time: 92.35%, memory: 36.57%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *pre = new ListNode(0);
        pre -> next = head;
        ListNode *p = pre, *q = pre;
        while(n--){
            q = q -> next;
        }
        while(q -> next){
            p = p -> next;
            q = q -> next;
        }
        p -> next = (p -> next) -> next;
        return pre -> next;
    }
};

206 反轉(zhuǎn)鏈表

按照題目要求，我采用了遞歸和迭代兩種做法，遞歸內(nèi)存占用要大一些，時間都差不多。

迭代做法，從左到右，把相鄰的兩個節(jié)點交換位置，其中一個是原來的head：

time: 98.36%, memory: 68.64%
/**
 * 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) return head;
        ListNode * pre = new ListNode(0);
        pre -> next = head;
        while(head -> next){
            ListNode * tmp = pre -> next;
            pre -> next = head -> next;
            head -> next = (head -> next) -> next;
            (pre -> next) -> next = tmp;
        }
        return pre -> next;
    }
};

遞歸做法，從右到左，把相鄰的兩個節(jié)點交換位置，其中一個節(jié)點是最后一個節(jié)點：

time: 98.36%, memory: 5.07%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> reverse_part(ListNode* head){
        vector<ListNode*> L;
        if(!(head -> next)){
            L.push_back(head);
            L.push_back(head);
            return L;
        }
        L = reverse_part(head -> next);
        L[1] -> next = head;
        head -> next = NULL;
        L[1] = head;
        return L;
    }
    ListNode* reverseList(ListNode* head) {
        if(!head) return head;
        vector<ListNode*> L = reverse_part(head);
        return L[0];
    }
};