2020-02-15 刷题 3（链表）

237 删除链表中的节点

刚开始读题有点迷惑，怎么就只给了一个node，又不是单链表，无法获取node的前驱，删除了node链表不就断了么。后来想到办法，先把node的后继的值复制到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 删除链表的倒数第n个节点

标签：双指针，链表
第一种解法是两次扫描的做法，为的是熟悉一下链表的操作。

leetcode的链表中，head指的就是第一个元素，不是哨兵节点，最后也没有尾哨兵节点，所以必要的时候，可以手动添加哨兵节点来方便操作，当然输出的时候别忘了删掉。

这里添加一个头哨兵节点，是为了处理第一个节点被删的情况。

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;  // 设置哨兵
        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;
    }
};

第二种做法是只扫描一遍的，设置两个指针，保持两个指针的距离始终为n，当右边的指针到达末尾时，左边的指针就到了要删除节点的前驱。
代码：

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 反转链表

按照题目要求，我采用了递归和迭代两种做法，递归内存占用要大一些，时间都差不多。

迭代做法，从左到右，把相邻的两个节点交换位置，其中一个是原来的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;
    }
};

递归做法，从右到左，把相邻的两个节点交换位置，其中一个节点是最后一个节点：

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