21-删除链表的倒数第N个节点

自己的做法

算法思想

和18-找到链表倒数第k个节点类似。使用两个指针right和left。right指针先向后走k步，然后两个指针同时向后走，直到right指针指向空，此时left指向的是倒数第k个节点。

但不同的是，18是找到倒数第k个节点，而该题是删除倒数第N个节点，所以需要找到倒数第N个节点的前一个节点。

还要考虑到边界问题，如删除第一个节点。

所以可以使用一个哨兵节点，即在头节点前添加一个节点，这样所有 有可能被删除的节点都是中间节点，不需要单独考虑边界问题。

不过要注意两个问题：

• 因为多了一个节点，所以如果righ初始指向哨兵节点，则right指针要走N + 1步
• 最后返回值记得返回哨兵节点的next。

算法实现

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * temp = new ListNode();
        temp->next = head;
        ListNode * left = temp;
        ListNode * right = temp;
        for (int i = 0; i <= n; ++i) {
            right = right->next;
        }
        while (right != nullptr) {
            left = left->next;
            right = right->next;
        }
        left->next = left->next->next;
        return temp->next;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

参考做法

给出了三个解法。第三个就是我自己的做法。

第一个做法是先遍历一遍，获得链表长度，然后删除。

第二个做法是使用栈来保存每个节点的指针，先依次将节点入栈，那么倒数第N个节点，就是弹出栈的第N个节点。

同时注意边界问题，即删除头节点。所以可以添加一个哨兵节点，再入栈。

时间复杂度是$O(n)$，空间复杂度也是$O(n)$。