LeetCode 题解工作台
螺旋矩阵 IV
给你两个整数： m 和 n ，表示矩阵的维数。 另给你一个整数链表的头节点 head 。 请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、 顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。 返回生成的矩阵。 示例 1： 输入…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们定义一个二维数组 ，用来存放链表中的元素，初始时全部填充为 。定义三个变量 $i, j, k$，分别表示当前的行、列和方向。定义一个数组 ，表示四个方向的偏移量。 然后我们开始遍历链表，每次遍历一个节点，就将当前节点的值填充到 中，然后更新链表的指针，如果链表为空，说明所有的元素都已经填充完毕，退出循环。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你两个整数：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
解题思路
方法一：模拟
我们定义一个二维数组 ，用来存放链表中的元素，初始时全部填充为 。定义三个变量 ，分别表示当前的行、列和方向。定义一个数组 ，表示四个方向的偏移量。
然后我们开始遍历链表，每次遍历一个节点，就将当前节点的值填充到 中，然后更新链表的指针，如果链表为空，说明所有的元素都已经填充完毕，退出循环。
否则，我们需要找到下一个元素的位置，我们可以通过当前位置 和当前方向 来计算下一个位置 ，如果 在矩阵的范围内，并且 为 ，说明 还没有被填充过，我们就将 作为下一个位置，否则我们需要更换方向。
遍历完链表之后，我们就得到了一个螺旋矩阵，返回即可。
时间复杂度 ，空间复杂度 。其中 和 分别表示矩阵的行数和列数。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
ans = [[-1] * n for _ in range(m)]
i = j = k = 0
dirs = (0, 1, 0, -1, 0)
while 1:
ans[i][j] = head.val
head = head.next
if head is None:
break
while 1:
x, y = i + dirs[k], j + dirs[k + 1]
if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
i, j = x, y
break
k = (k + 1) % 4
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot m) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to implement linked-list pointer manipulation effectively.
- question_mark
Evaluate how they manage matrix traversal boundaries and handle edge cases.
- question_mark
Check if they handle the matrix's unfilled spaces correctly when the list is smaller.
常见陷阱
外企场景- error
Forgetting to initialize the matrix with -1s before filling it.
- error
Not properly updating the boundaries while performing the spiral traversal.
- error
Incorrectly handling cases where the linked list is shorter than the matrix.
进阶变体
外企场景- arrow_right_alt
Increase the matrix dimensions to test if the candidate can handle larger inputs.
- arrow_right_alt
Challenge the candidate with linked lists that have exactly m * n elements.
- arrow_right_alt
Test the candidate with a very small matrix (e.g., m = 1, n = 1).