Delete node from the end of the linked list for the given index

Question

I'm trying to solve LeetCode problem 19. Remove Nth Node From End of List :

Given the head of a linked list, remove the n^th 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]

This is the code I wrote:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count = 0;
        while (head->next!=NULL){
            head = head -> next ;
            count++;
        }
        int len;
        len = count - n ;
        ListNode* curr = head; 
        for(int i =len ; i > 0 ; i--){
            curr = curr->next;
        }
        curr->next = curr->next->next;
        return head;

    }
};

I get this error:

Line 23: Char 26: runtime error: member access within null pointer of type 'ListNode' (solution.cpp)

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:32:26

Can someone tell what is wrong in the code, that it raises this error?

Answer 1

There are a few issues:

• The first loop makes head reference the last node in the list. But that means your second loop will start from there, not from the first node of the list. And so in the first iteration of the second loop, curr = curr->next will assign nullptr to curr, and its second iteration will run into the error you saw. You should not use head as a tool to traverse the list. Use a separate variable for that.

• The similar error will occur when the node to remove is the last node in the list. In that case the expression curr->next->next will raise the error. curr->next is null in that case. You should deal with this boundary case and first verify whether curr->next is null and act accordingly.

• Your code does not foresee the case where the first node needs to be removed, which means you have to return the successor of head.

(Not a problem, but NULL should not be used in C++ code, use nullptr).

Here is your code with the corrections needed to fix these three issues:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count = 0;
        ListNode* curr = head; // Use a different variable for the traversal
        while (curr->next) { // Don't use NULL
            curr = curr -> next ;
            count++;
        }
        int len;
        len = count - n;
        if (len < 0) { // Deal with removal of first node
            return head->next;
        }
        curr = head; 
        for (int i = len ; i > 0 ; i--) {
            curr = curr->next;
        }
        // Deal with removal of last node (when curr->next is nullptr)
        curr->next = curr->next ? curr->next->next : nullptr;
        return head;
    }
};