题解 | #删除链表的倒数第n个节点#

只要能得到倒数第n个结点前一个结点，就能实现删除结点。该题的重点是如何得到倒数第n个结点的前置结点。

方法一：

1、遍历链表得到链表的长度length；

2、倒数第n个结点即为正数第(length - n - 1)个结点，再遍历链表至第(length - n)结点，即可完成删除。

可以发现对链表的操作，很多情况需要设置表头，这样是为了便于对头结点进行操作

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //特殊情况处理
        if (head == nullptr)
            return nullptr;
        //设置表头
        ListNode* res = new ListNode(0);
        res->next = head;
        ListNode* ptemp = res;
        int length = 0;
        //得到链表的长度
        while (ptemp->next != nullptr) {
            ptemp = ptemp->next;
            length++;
        }
        //遍历至需要删除的结点前面一个结点
        ptemp = res;
        for (int i = 0; i < length - n; i++) {
            ptemp = ptemp->next;
        }
        //删除结点
        ptemp->next = ptemp->next->next;
        return res->next;
    }
};

方法二：

1、使用两个指针fast 和 slow 同时对链表进行遍历，fast 比 slow 超前 n 个节点。当 fast 遍历到链表的末尾时，slow 就恰好处于倒数第 n 个节点。

在链表中善用快慢指针可以得到链表中的任意位置结点，例如得到链表的中间结点等。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == nullptr)
            return nullptr;

        ListNode* res = new ListNode(0);
        res->next = head;
        ListNode* pnode = res;

        ListNode* ptemp = head;
        for (int i = 0; i < n; i++) {
            ptemp = ptemp->next;
        }

        while (ptemp != nullptr) {
            pnode = pnode->next;
            ptemp = ptemp->next;
        }
        pnode->next = pnode->next->next;
        return res->next;
    }
};