Runtime error when deleting the middle node of a linked list

Question

I am working on LeetCode problem 2095. Delete the Middle Node of a Linked List:

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋^th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

• For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

This is my code

/**
 * 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* deleteMiddle(ListNode* head) {
        
        ListNode *slow = head ;
        ListNode *fast = head ;
        
        
        if(head==NULL){
            return head ;
        } 
        if(head->next == NULL){
            delete head ;
            return head ;
        }
        
        while(fast->next && fast){
            slow = slow->next ;
            fast = fast->next->next ;
        } 
        
        ListNode *temp = head ;
        
        while(temp->next != slow){
            temp=temp->next ;
        } 
        
        
        temp->next = slow->next ;
        delete slow ;
        
        return head ;
        
        
    }
};

I am getting runtime error as follows:

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

What am I doing wrong?

Answer 1

There are two issues:

• After delete head you should not do return head as then you return a reference to freed memory, and the testing platform will certainly access that in order to test the result, leading to undefined behavior (or this error you got). Instead, you should return nullptr

• The while condition should first check that fast is not nullptr before checking what fast->next is, so these conditions should appear in reversed order.

With those fixes it will work.

Still, it is a pity that your code needs yet another pointer (temp) to walk through the list in order to find the node that precedes slow. It would be better to make sure slow is pointing to that preceding node to begin with... then you don't need that extra traversal through the list. You can achieve this by giving fast two steps advantage before starting the (first) loop.

Here is the code with the two problems fixed, and with the improvement I mentioned above:

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        
        if (head->next == nullptr) {
            delete head;
            return nullptr; // Don't return a reference to freed memory!
        }

        ListNode *slow = head;
        // Already advance `fast` with 2 steps, 
        //   so `slow` ends up BEFORE the node to delete
        ListNode *fast = head->next->next; 
        
        // First check that the fast pointer is not nullptr before accessing `->next`
        while (fast && fast->next) { 
            slow = slow->next;
            fast = fast->next->next;
        } 
        
        // No need for `temp` when we make sure `slow` is at the preceding spot
        // Reuse `fast` for referencing the node to delete
        fast = slow->next;
        slow->next = fast->next;
        delete fast;
        
        return head;
    }
};