Spiral matrix challenge: member access within null pointer of type 'ListNode'

Question

I am working on LeetCode problem 2326. Spiral Matrix IV:

You are given two integers m and n, which represent the dimensions of a matrix.

You are also given the head of a linked list of integers.

Generate an m x n matrix that contains the integers in the linked list presented in spiral order (clockwise), starting from the top-left of the matrix. If there are remaining empty spaces, fill them with -1.

Return the generated matrix.

I am trying to solve it using 4 different pointers pointing to the edges of the matrix between which our linked list is travelling and storing the value of the linked list node inside the matrix.

But I get this error:

Line 46: Char 56: runtime error: member access with null pointer of type 'ListNode' (solution.cpp)

SUMMARY: UndefinedBahaviorSanitizer: indefined-behavior prog_joined.cpp:55:46

Here is my code:

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>>ans(m,vector<int>(n,-1));
        int top=0;
        int bottom=m-1;
        int left=0;
        int right=n-1;
        int dir=0;
        
        while(head){
            switch(dir){
                    
                case 0:{
                    for(int i=left;i<right;i++){
                        ans[top][i]=head->val;
                        head=head->next;
                    }
                    top++;
                    dir=(dir+1)%4;
                    break;
                }
                    
                case 1:{
                    for(int i=top;i<bottom;i++){
                        ans[i][right]=head->val;
                        head=head->next;
                    }
                    right--;
                    dir=(dir+1)%4;
                    break;
                }
                
                case 2:{
                    for(int i=right;i>=left;--i){
                        ans[bottom][i]=head->val;
                        head=head->next;
                    }
                    bottom--;
                    dir=(dir+1)%4;
                    break;
                }
                    
                case 3:{
                    for(int i=bottom;i>=top;--i){
                        ans[i][left]=head->val;
                        head=head->next;
                    }
                    left++;
                    dir=(dir+1)%4;
                    break;   
                }
                    
            }
        }
        return ans;
    }
};

What is causing the error?

Answer 1

Some issues:

• The inner loops do not check whether head is nullptr and risk making an invalid reference with head->next
• As you have defined bottom and right as inclusive (initialising them with m-1 and n-1), you would need to align the inner loop condition accordingly with i<=bottom and i<=right.

I would further suggest to not have inner loops, but maintain the current position (row/col) in the matrix and only fill in one value per iteration of the outer loop. This way there is only one test needed for head.

You can also avoid code repetition and use variables to determine which boundary to check and which change to make to the current position (row/col).

Here is how that could look:

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m, vector<int>(n, -1));
        int boundary[4] = {0, n-1, m-1, 0}; // Top, Rightend, Bottom, Leftend
        int direction[4] = {-1, 1, 1, -1}; // Up, Right, Down, Left
        int index[2] = {0, 0}; // Row, Column
        int dir = 1; // Right

        while (head) {
            ans[index[0]][index[1]] = head->val;
            head = head->next;
            if (index[dir % 2] == boundary[dir]) {
                dir = (dir + 1) % 4;
                boundary[dir ^ 2] += direction[dir];
            }
            index[dir % 2] += direction[dir];
        }
        return ans;
    }
};