I am working on LeetCode problem 19. Remove Nth Node From End of List:

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

This is my code:

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;
    }
};

I get this error when one of the test cases is run:

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

Not sure why I'm getting this error, because according to what I think, both t and q are not NULL here at the moment. So, I shouldn't have gotten this error.

CodePudding user response：

according to what I think, both t and q are not NULL

...not when n is equal to the size of the list, in which case c will be 0 after c=c-n is executed. In that case the second loop will make no iterations, leaving t equal to NULL (BTW, you should really be using nullptr in C ).

In that boundary case, you need to remove the first node, and return a different head pointer.

So replace:

        t->next=q->next;

with

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

CodePudding user response：

You assign q = head and then run this loop.

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

But what happens if head is nullptr? Then t is still nullptr.

Then it makes this line crash.

t->next=q->next;

So, you can check head is not nullptr at the beginning, OR you can check t is not nullptr before using it.

CodePudding user response：

Leetcode will teach you how to solve problems but it will not teach you good C . C comes with a lot of build in datastructures and algorithms that should be used instead of the coding style shown on leetcode. Compare this code with the typical examples on leetcode and you might get a feel for that difference. (including giving variables readable names and writing small functions to increase readability)

E.g. Use C 's std::list instead of writing your own

#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;
}