Spiral Matrix IV

• Create an m x n result matrix matrix and initialize all its elements to -1.
• Create an m x n boolean matrix visited and initialize all its elements to false.
• Initialize the starting position (row, col) to (0, 0) and the initial direction dir to 0 (representing 'right').
• Define direction vectors for row and column changes: dr = {0, 1, 0, -1} and dc = {1, 0, -1, 0}.
• Use a pointer curr to traverse the linked list, starting from the head.
• Loop as long as curr is not null:
  1. Place the value curr.val at matrix[row][col].
  2. Mark the cell as visited: visited[row][col] = true.
  3. Advance the list pointer: curr = curr.next.
  4. If the list is exhausted, break the loop.
  5. Calculate the next potential position (nextRow, nextCol) using the current direction.
  6. If (nextRow, nextCol) is out of bounds or has already been visited, change the direction by turning clockwise: dir = (dir + 1) % 4.
  7. Update the current position (row, col) using the new direction.
• Return the matrix.

In this method, we simulate the path of a point moving through the matrix. We begin by creating the m x n result matrix and pre-filling it with -1. This handles the requirement for default values in unused cells. We also need a second m x n boolean matrix, visited, to keep track of which cells have been filled.

The traversal starts at the top-left corner (0, 0). We maintain the current direction of travel (e.g., right, down, left, up). We iterate as long as there are nodes left in the linked list. In each step, we fill the current cell, mark it as visited, and advance the linked list pointer. Then, we check if the next cell in the current direction is valid (i.e., within the matrix boundaries and not yet visited). If it's not valid, we know we've hit a wall or a previously filled path, so we turn clockwise to the next direction. Finally, we update our current coordinates to move to the next cell. This process naturally carves out a spiral path.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public int[][] spiralMatrix(int m, int n, ListNode head) {13        int[][] matrix = new int[m][n];14        for (int i = 0; i < m; i++) {15            java.util.Arrays.fill(matrix[i], -1);16        }17 18        boolean[][] visited = new boolean[m][n];19        int[] dr = {0, 1, 0, -1}; // Direction vectors for row20        int[] dc = {1, 0, -1, 0}; // Direction vectors for col21        int row = 0, col = 0, dir = 0;22        ListNode curr = head;23 24        // We can iterate m * n times, as that's the max number of cells to fill.25        for (int i = 0; i < m * n; i++) {26            if (curr == null) {27                break;28            }29            matrix[row][col] = curr.val;30            visited[row][col] = true;31            curr = curr.next;32 33            int nextRow = row + dr[dir];34            int nextCol = col + dc[dir];35 36            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol]) {37                dir = (dir + 1) % 4; // Change direction38            }39            40            row += dr[dir];41            col += dc[dir];42        }43 44        return matrix;45    }46}

• Create an m x n result matrix matrix and initialize all its elements to -1.
• Initialize four boundary pointers: top = 0, bottom = m - 1, left = 0, right = n - 1.
• Use a pointer curr to traverse the linked list, starting from the head.
• Loop as long as top <= bottom and left <= right.
  1. Traverse Right: Iterate from j = left to right. In each step, if curr is not null, set matrix[top][j] = curr.val and advance curr. After the row is filled, increment top.
  2. Traverse Down: Iterate from i = top to bottom. If curr is not null, set matrix[i][right] = curr.val and advance curr. After the column is filled, decrement right.
  3. Traverse Left: Check if top <= bottom. If so, iterate from j = right to left. If curr is not null, set matrix[bottom][j] = curr.val and advance curr. After the row is filled, decrement bottom.
  4. Traverse Up: Check if left <= right. If so, iterate from i = bottom to top. If curr is not null, set matrix[i][left] = curr.val and advance curr. After the column is filled, increment left.
• If curr becomes null at any point, the loops will continue but won't fill any more cells, effectively terminating the process.
• Return the matrix.

This optimal approach avoids the need for an extra visited matrix by intelligently shrinking the boundaries of the matrix after each full pass of a row or column. We start by initializing the m x n result matrix with -1.

We define four pointers: top, bottom, left, and right, which represent the boundaries of the current rectangular layer we are filling. Initially, they correspond to the full matrix dimensions.

The process is a loop that continues as long as the boundaries have not crossed (i.e., top <= bottom and left <= right) and we still have nodes in our linked list.

Inside the loop, we perform four distinct steps to fill the four sides of the current layer in a clockwise direction:

1. Fill the top row from left to right.
2. Fill the rightmost column from top to bottom.
3. Fill the bottom row from right to left.
4. Fill the leftmost column from bottom to top.

After each step, we update the corresponding boundary pointer (e.g., after filling the top row, we increment top) to shrink the area for the next iteration. We must also check if the linked list has been exhausted before filling each cell. The conditions if (top <= bottom) and if (left <= right) are crucial before the third and fourth steps to handle matrices that are not square (e.g., a single row or column).

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public int[][] spiralMatrix(int m, int n, ListNode head) {13        int[][] matrix = new int[m][n];14        for (int i = 0; i < m; i++) {15            java.util.Arrays.fill(matrix[i], -1);16        }17 18        int top = 0, bottom = m - 1;19        int left = 0, right = n - 1;20        ListNode curr = head;21 22        while (curr != null && top <= bottom && left <= right) {23            // Traverse Right24            for (int j = left; j <= right && curr != null; j++) {25                matrix[top][j] = curr.val;26                curr = curr.next;27            }28            top++;29 30            // Traverse Down31            for (int i = top; i <= bottom && curr != null; i++) {32                matrix[i][right] = curr.val;33                curr = curr.next;34            }35            right--;36 37            // Traverse Left (check if row still exists)38            if (top <= bottom) {39                for (int j = right; j >= left && curr != null; j--) {40                    matrix[bottom][j] = curr.val;41                    curr = curr.next;42                }43                bottom--;44            }45 46            // Traverse Up (check if column still exists)47            if (left <= right) {48                for (int i = bottom; i >= top && curr != null; i--) {49                    matrix[i][left] = curr.val;50                    curr = curr.next;51                }52                left++;53            }54        }55        return matrix;56    }57}