6111. 螺旋矩阵 IV题目（中等）

给你两个整数：m 和 n ，表示矩阵的维数。

另给你一个整数链表的头节点 head 。

请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。

返回生成的矩阵。

示例 1：

 输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0] 输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]] 解释：上图展示了链表中的整数在矩阵中是如何排布的。 注意，矩阵中剩下的空格用 -1 填充。

示例 2：

 输入：m = 1, n = 4, head = [0,1,2] 输出：[[0,1,2,-1]] 解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。  注意，矩阵中剩下的空格用 -1 填充。

提示：

1 <= m, n <= 1051 <= m * n <= 105链表中节点数目在范围 [1, m * n] 内0 <= Node.val <= 1000解题思路方法一：模拟（按层模拟）

将螺旋矩阵看成由若干层组成的，一层层填充空格，直至填到最内层。

定义每层左上角空格为 (top, left)、右下角为 (bottom, right)，按上图所示，顺时针一段段的填充矩阵：

(top, left) 到 (top, right)(top + 1, right) 到 (bottom, right)当 bottom > top 时，(bottom, right - 1) 到 (bottom, left)，即 bottom 和 top 不是在一行当 left < right 时，(bottom, left) 到 (top + 1, left)，即left 和 right 不是在一列

填充完当前层后，left 和 top 增加一，right 和 bottom 减少一，进入下一层继续填充，直至填完。

复杂度分析时间复杂度：O(mn)。空间复杂度：O(mn)。方法二：模拟

按照题意直接模拟，首先将矩阵全部填充为 -1，然后沿向左方向开始填充矩阵，当填充到矩阵边界或者已经填充的格子时，则改变方向继续填充。填充方向设置为向左、向下、向右、向上，每当填充到边界或已填充的格子时，就改变方向，直至链表中的元素填充完毕。

复杂度分析时间复杂度：O(mn)。空间复杂度：O(mn)。代码

 /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode() {}  *     ListNode(int val) { this.val = val; }  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  * }  */ class Solution {     public int[][] spiralMatrix(int m, int n, ListNode head) {         int[][] ans = new int[m][n];         int t = 0, l = 0, b = m - 1, r = n - 1;         while (t <= b && l <= r) {             for (int j = l; j <= r; j++) {                 ans[t][j] = head == null ? -1 : head.val;                 if (head != null) head = head.next;             }             t++;             for (int i = t; i <= b; i++) {                 ans[i][r] = head == null ? -1 : head.val;                 if (head != null) head = head.next;             }             r--;             if (b > t) {                 for (int j = r; j >= l; j--) {                     ans[b][j] = head == null ? -1 : head.val;                     if (head != null) head = head.next;                 }                 b--;             }             if (l < r) {                 for (int i = b; i >= t; i--) {                     ans[i][l] = head == null ? -1 : head.val;                     if (head != null) head = head.next;                 }                 l++;             }         }         return ans;     } }

 /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode() {}  *     ListNode(int val) { this.val = val; }  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  * }  */ class Solution {     public int[][] spiralMatrix(int m, int n, ListNode head) {         // 初始化答案矩阵值为-1         int[][] ans = new int[m][n];         for (int i = 0; i < m; i++) {             Arrays.fill(ans[i], -1);         }         // 顺时针填充矩阵         int[] dx = {0, 1, 0, -1};         int[] dy = {1, 0, -1, 0};         int x = 0, y = 0, d = 0;         while (true) {             ans[x][y] = head.val;             head = head.next;             // 链表已经遍历完，退出             if (head == null) {                 break;             }             // 计算下一个位置坐标             while (true) {                 // 尝试往前走一步                 int nx = x + dx[d];                 int ny = y + dy[d];                 // 走出矩阵或走到已填充位置，换一个方向                 if (nx < 0 || ny < 0 || nx >= m || ny >= n || ans[nx][ny] != -1) {                     d = (d + 1) % 4;                     continue;                 }                 // 走到下一个要填充位置                 x = nx;                 y = ny;                 break;             }         }         return ans;     } }

题目链接：