跳转至

删除链表的倒数第 N 个结点⚓︎

Leetcode题目链接

描述⚓︎

详见中文题目链接。

解答⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummyHead = new ListNode(0);
        dummyHead->next = head;

        int len = 0;
        for (auto p = dummyHead; p; p = p->next) len++;

        auto p = dummyHead;
        for (int i = 0; i < len - n - 1; i++) p = p->next;
        p->next = p->next->next;

        return dummyHead->next;
    }
};

最后那个p从虚拟头结点开始，为什么跳1步是到第二个点呢？不应该是到第一个点吗？

因为把虚拟头结点算作第一个点了，总数n里包含了虚拟头结点。而虚拟头结点在链表头部所以不影响倒数第k个数。倒数第k个数是正数第n + 1 - k个数，那么倒数第k + 1就是正数n - k个数，第一个数跳到第二个数需要1步，那么第一个数跳到第n - k个数，一共需要n-k-1步。