Leetcode问题19中的运行时错误--从列表末尾删除第n个节点

Question

我正在研究LeetCode problem 19.从列表末尾删除N节点

给定链接列表的head，从列表末尾移除第n个节点并返回它的头。 示例1： 投入:头= 1,2,3,4,5，n=2产出: 1,2,3,5 制约因素：

• 列表中的节点数为sz。
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

这是我的密码：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p=head,*q=head,*t=NULL;
        long long  c=0;
        while(p!=0){
            c++;
            p=p->next;
        }
        c=c-n;
        while(q!=NULL && c>0){
            t=q;
            q=q->next;
            c--;
        }
        t->next=q->next;
        delete q;
        return head;
    }
};

当其中一个测试用例运行时，我得到了这个错误：

Line 26: Char 12: runtime error: 
         member access within null pointer of type 'ListNode' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:35:12

不知道为什么会出现这个错误，因为根据我的想法，t和q目前都不是NULL。所以，我不该犯这个错误。

Answer 1

根据我的看法，t和q都不是空的。

...not时，n等于列表的大小，在执行c=c-n后，c将为0。在这种情况下，第二个循环将不进行迭代，使得t等于NULL (BTW，您应该在C++中真正使用nullptr )。

在这种边界情况下，您需要删除第一个节点，并返回一个不同的head指针。

因此，替换：

        t->next=q->next;

使用

        if (t == nullptr) {
            head = q->next;
        } else {
            t->next = q->next;
        }

Answer 2

分配q = head，然后运行这个循环。

while(q!=NULL && c>0){
            t=q;
            q=q->next;
            c--;
}

但是如果head是nullptr会发生什么呢？那么t仍然是nullptr。

然后这条线就会崩溃。

t->next=q->next;

因此，您可以在开始时检查head不是nullptr，也可以在使用它之前检查t不是nullptr。

Answer 3

Leetcode会教你如何解决问题，但它不会教你好的C++。C++提供了大量的数据结构和算法构建，它们应该被使用，而不是leetcode中显示的编码风格。将此代码与leetcode上的典型示例进行比较，您可能会感觉到这种差异。(包括提供变量可读的名称和编写小函数以提高可读性)

使用C++的std::list，而不是自己写。

#include <stdexcept>
#include <list>
#include <iostream>

void erase_pos_from_last(std::list<int>& list, std::size_t pos)
{
    // never trust your input!
    if (pos >= list.size())
    {
        return; // do nothing
        // or throw std::invalid_argument("pos cannot be larger then the size of your list");
    }

    auto last = list.size() - 1;
    auto it = list.begin();
    std::advance(it, last - pos);
    list.erase(it);
}


int main()
{
    std::list<int> values{ 1,2,3,4,5,6,7 };
    erase_pos_from_last(values,6ul);
    

    for (const auto& value : values)
    {
        std::cout << value << " ";
    }

    return 0;
}