还是 two pointers 啊。

继续，继续。

876. Middle of the Linked List

Analysis

找链表的中间结点，比较常规的一道题。

Code

method 1

单指针需要遍历两次链表，略麻烦。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode *tmp = head;
        int cnt = 0;
        while(tmp) {
            cnt++;
            tmp = tmp->next;
        }
        tmp = head;
        for(int i = 0; i < cnt / 2; i++) tmp = tmp->next;
        return tmp;
    }
};

method 2

双指针只用遍历一次链表，但要注意判空的条件。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode *slow = head, *fast = head;
        while(fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

method 3

没想到官方提供了一种数组的题解，不过与其说是数组，不如说是队列。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr) return nullptr;
        vector<ListNode*> arr = {head};
        while(arr.back()->next != nullptr) {
            arr.push_back(arr.back()->next);
        }
        return arr[arr.size() / 2];
    }
};

19. Remove Nth Node From End of List

Analysis

删除链表的的倒数第 n 个结点，这也是个很常规的题目。

Code

method 1

假设总结点数是 N，只用一个指针时，删除倒数第 n 个结点，就是删除正数第 N - n 个结点，所以要计算一下链表的长度，另外还需要考虑一下删除的是不是第一个结点了。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return nullptr;
        ListNode* tmp = head;
        int cnt = 0;
        while(tmp != nullptr) {
            cnt++;
            tmp = tmp->next;
        }
        cnt -= n;
        tmp = head;
        ListNode* t;
        if(cnt == 0) {
            t = head->next;
            head = t->next;
        } else {
            for(int i = 0; i < cnt - 1; i++) tmp = tmp->next;
            t = tmp->next;
            tmp->next = t->next;
        }
        delete(t);
        return head;
    }
};

method 2

用双指针的解法，与单指针类似。但是如果在一开始加一个头结点话，删除结点时，就不用太考虑是否是第一个结点了。这种在表头加的结点叫做哑结点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return nullptr;
        ListNode *dummy = new ListNode(0, head);
        ListNode *first = head;
        ListNode *second = dummy;
        for(int i = 0; i < n; i++) first = first->next;
        while(first != nullptr) {
            first = first->next;
            second = second->next;
        }
        first = second->next;
        second->next = first->next;
        delete(first);
        first = dummy->next;
        delete(dummy);
        return first;
    }
};

method 3

用栈也可以做。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return nullptr;
        ListNode *dummy = new ListNode(0, head);
        stack<ListNode*> st;
        ListNode *tmp = dummy;
        while(tmp != nullptr) {
            st.push(tmp);
            tmp = tmp->next;
        }
        for(int i = 0; i < n; i++) {
            st.pop();
        }
        ListNode *pre = st.top();
        tmp = pre->next;
        pre->next = tmp->next;
        delete(tmp);
        pre = dummy->next;
        delete(dummy);
        return pre;
    }
};

method 4

看评论，发现竟然还能用递归做😂，递归边界是遍历到链表表尾，判定条件是访问的结点数等于要删除的结点位置。不得不说，用递归来解决这个问题很巧。

class Solution {
public:
    int cur = 0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return nullptr;
        head->next = removeNthFromEnd(head->next, n);
        cur++;
        if(n == cur) return head->next;
        return head;
    }
};

Summary

今天是两个很常规的题目，不算难题，自己想也比较容易解决，就是可能想不到多种方法来解决这些问题。还有一个很奇怪的地方，按理说，即便加了哑结点，在不改变 head 的情况下，直接返回 head 应该是不会错误的。但是，address sanitizer 会报错，是有潜在的内存错误吗？🤔