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

剛開(kāi)始讀題有點(diǎn)迷惑，怎么就只給了一個(gè)node，又不是單鏈表挪丢，無(wú)法獲取node的前驅(qū)，刪除了node鏈表不就斷了么卢厂。后來(lái)想到辦法乾蓬，先把node的后繼的值復(fù)制到node中，然后node指向后繼的后繼慎恒，最后把node原來(lái)的后繼刪掉任内。還是挺巧妙的題目。
代碼：

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個(gè)節(jié)點(diǎn)

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

leetcode的鏈表中粒氧，head指的就是第一個(gè)元素越除，不是哨兵節(jié)點(diǎn)，最后也沒(méi)有尾哨兵節(jié)點(diǎn)外盯，所以必要的時(shí)候摘盆，可以手動(dòng)添加哨兵節(jié)點(diǎn)來(lái)方便操作，當(dāng)然輸出的時(shí)候別忘了刪掉饱苟。

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

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è)置兩個(gè)指針肋殴，保持兩個(gè)指針的距離始終為n囤锉，當(dāng)右邊的指針到達(dá)末尾時(shí)坦弟，左邊的指針就到了要?jiǎng)h除節(jié)點(diǎn)的前驅(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)存占用要大一些烙懦，時(shí)間都差不多。

迭代做法赤炒，從左到右氯析，把相鄰的兩個(gè)節(jié)點(diǎn)交換位置，其中一個(gè)是原來(lái)的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;
    }
};

遞歸做法莺褒，從右到左掩缓，把相鄰的兩個(gè)節(jié)點(diǎn)交換位置，其中一個(gè)節(jié)點(diǎn)是最后一個(gè)節(jié)點(diǎn)：

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