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.

&nbsp;
Example 1:

Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
Explanation: The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.


Example 2:

Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

&nbsp;
Constraints:


	1 &lt;= m, n &lt;= 105
	1 &lt;= m * n &lt;= 105
	The number of nodes in the list is in the range [1, m * n].
	0 &lt;= Node.val &lt;= 1000


class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        num = m * n
        res = [[-1 for j in range(n)] for i in range(m)]
        x, y = 0, 0
        dx, dy = 1, 0
        while head:
            res[y][x] = head.val
            if x + dx < 0 or x + dx >= n or y + dy < 0 or y + dy >= m or res[y+dy][x+dx] != -1:
                dx, dy = -dy, dx
            x = x + dx
            y = y + dy
            head = head.next
        return res
class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] ans=new int[m][n];
        for(int[] arr:ans){
            Arrays.fill(arr,-1);
        }
        
        int rowBegin=0;
        int rowEnd=m-1;
        int columnBegin=0;
        int columnEnd=n-1;
        ListNode cur=head;
        
      
        while(rowBegin<=rowEnd && columnBegin<=columnEnd && cur!=null){
            
            for(int i=columnBegin;i<=columnEnd && cur!=null;i++){
                if(cur!=null){
                    ans[rowBegin][i]=cur.val;
                }
               
                    cur=cur.next;
                
                
            }
            rowBegin++;
            for(int i=rowBegin;i<=rowEnd && cur!=null;i++){
               if(cur!=null){
                ans[i][columnEnd]=cur.val;
               }
                
                    cur=cur.next;
                

            }
            columnEnd--;
            if(rowBegin<=rowEnd){
                for(int i=columnEnd;i>=columnBegin && cur!=null;i--){
                if(cur!=null){
                ans[rowEnd][i]=cur.val;
                }
                 
                    cur=cur.next;
                

            }
           
            }
             rowEnd--;
            if(columnBegin<=columnEnd){
                for(int i=rowEnd;i>=rowBegin && cur!=null;i--){
                  if(cur!=null){
                ans[i][columnBegin]=cur.val;
                  }
                 
                    cur=cur.next;
                

            }
            
            }
            columnBegin++;
           
        }
        return ans;
        
    }
}
class Solution {
public:
    vector<vector<int>> spiralMatrix(int n, int m, ListNode* head) 
    {
		// Create a matrix of n x m with values filled with -1.
        vector<vector<int>> spiral(n, vector<int>(m, -1));
        int i = 0, j = 0;
		// Traverse the matrix in spiral form, and update with the values present in the head list.
		// If head reacher NULL pointer break out from the loop, and return the spiral matrix.
        while (head != NULL)
        {
            if (j < m)
            {
                while (head != NULL && j < m && spiral[i][j] == -1)
                {
                    spiral[i][j] = head->val;
                    head = head->next;
                    j++;
                }
                if (head == NULL)
                    break;
                i++;
                j--;
            }
            if (i < n)
            {
                while (head != NULL && i < n && spiral[i][j] == -1)
                {
                    spiral[i][j] = head->val;
                    head = head->next;
                    i++;
                }
                i--;
                j--;
            }
            if (j >= 0)
            {
                while (head != NULL && j >= 0 && spiral[i][j] == -1)
                {
                    spiral[i][j] = head->val;
                    head = head->next;
                    j--;
                }
                j++;
                i--;
            }
            if (i >= 0)
            {
                while (head != NULL && i >= 0 && spiral[i][j] == -1)
                {
                    spiral[i][j] = head->val;
                    head = head->next;
                    i--;
                }
                i++;
                j++;
            }
            n--;
            m++;
        }
		// Rest values are itself -1.
        return spiral;
    }
};
 var spiralMatrix = function(m, n, head) {
    var matrix = new Array(m).fill().map(()=> new Array(n).fill(-1))
    var row=0, col=0;
    var direction="right";
    while(head)
        {
            matrix[row][col]=head.val;
            if(direction=="right")
                {
                    if(col+1 == n || matrix[row][col+1] != -1)
                        {
                            direction="down"
                            row++;
                        }
                    else
                        col++
                }
            else if(direction=="down")
                {
                    if(row+1 == m || matrix[row+1][col] != -1)
                        {
                            direction="left"
                            col--;
                        }
                    else
                        row++
                }
            else if(direction=="left")
                {
                    if(col == 0 || matrix[row][col-1] != -1)
                        {
                            direction="up"
                            row--;
                        }
                    else
                        col--
                }
            else if(direction=="up")
                {
                    if(row == 0 || matrix[row-1][col] != -1)
                        {
                            direction="right"
                            col++;
                        }
                    else
                        row--
                }
            head = head.next;
        }
    return matrix;
};
Spiral Matrix IV