Runtime Error in Leetcode problem 19 -- remove nth node from end of list

Question

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.

Recommendation: Don't write alphabet soup. Give things descriptive names. — user4581301
– user4581301, Commented Nov 4, 2022 at 5:30
Consider using a stack. As you iterate through the list, add a pointer to each item to the stack. Then all you need to do is pop n times to find the node you need to remove. Also worth making sure that some jerk doesn't give a n larger than the list. — user4581301
– user4581301, Commented Nov 4, 2022 at 5:33
Run your code in a debugger and feed in the input set that causes failure. Then step until you see something you don't expect. — user4581301
– user4581301, Commented Nov 4, 2022 at 5:35
Also a good idea to test your code with the same sanitizers turned on. That means you need a compiler with sanitizers enabled and on Windows this usually means clang. — user4581301
– user4581301, Commented Nov 4, 2022 at 5:42
What happens when you try and remove the 0th from the end? godbolt.org/z/MEx7YrhMG — Retired Ninja
– Retired Ninja, Commented Nov 4, 2022 at 5:45

trincot · Accepted Answer · 2022-11-04 06:37:02Z

0

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

answered Nov 4, 2022 at 6:37

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

GAVD · Accepted Answer · 2022-11-04 06:42:37Z

0

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.

answered Nov 4, 2022 at 6:42

GAVD

2,1343 gold badges24 silver badges44 bronze badges

Comments

Pepijn Kramer · Accepted Answer · 2022-11-04 08:01:19Z

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

Collectives™ on Stack Overflow

Runtime Error in Leetcode problem 19 -- remove nth node from end of list

Example 1:

Constraints:

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example 1:

Constraints:

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related