§1

题目描述

给定整数 m 和 n,以及一条链表的头节点 head。生成一个 m 行 n 列的矩阵,把链表中的所有整数从矩阵左上角出发、按顺时针螺旋顺序依次填入。若填完链表后矩阵仍有空位,用 -1 补齐。返回这个矩阵。链表节点数不超过 m 乘 n,节点值在 0 到 1000 之间。

输入 = m=3, n=4, head=[3,7,1,9,4,8,2,6]　输出 = [[3,7,1,9],[-1,-1,-1,4],[-1,6,2,8]]

输入 = m=1, n=4, head=[0,1,2]　输出 = [[0,1,2,-1]]

§2

思路解析动画文字版

记牢这一句:走不走得动,只看下一格是不是「界内且还是 -1」。是就走,不是就顺时针转向。这一条判断,既管住了拐弯,也顺手把剩余格子留成了 -1。下面从左上角开始一步步走。

起点就位 · 指针在 (0,0),方向向右：开工前先把整张 3 乘 4 的矩阵在心里铺成 -1,舞台上没写过的格子先用一个点占位。指针停在左上角 (0,0),初始方向是向右。侧栏那一列 3、7、1、9、4、8、2、6,就是链表从头到尾要写进来的 8 个值。准备好了,开始沿螺旋往里填。

写入 3 到 (0,0)：第一步最简单:直接在起点 (0,0) 写下链表头的值 3,这一格变成紫色表示刚写。链表指针往后挪一位,侧栏顶上的 3 划走了。接着要决定下一格往哪儿走。

直行向右 · 走向 (0,1)：站在刚写完的这一格,判断下一步。朝向右探一格,下一格 (0,1) 在界内、而且还是 -1,没填过,直接迈过去。

写入 7 到 (0,1)：把链表当前值 7 写进 (0,1),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 2 个格子。

直行向右 · 走向 (0,2)：站在刚写完的这一格,判断下一步。朝向右探一格,下一格 (0,2) 在界内、而且还是 -1,没填过,直接迈过去。

写入 1 到 (0,2)：把链表当前值 1 写进 (0,2),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 3 个格子。

直行向右 · 走向 (0,3)：站在刚写完的这一格,判断下一步。朝向右探一格,下一格 (0,3) 在界内、而且还是 -1,没填过,直接迈过去。

写入 9 到 (0,3)：把链表当前值 9 写进 (0,3),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 4 个格子。

拐弯 · 转到向下,走向 (1,3)：站在刚写完的这一格,判断下一步。朝向右探一格会走出矩阵,于是顺时针转到向下,探到 (1,3) 在界内又还是 -1,迈过去。注意转向不是数着走了几步才拐,而是探到走不动的那一刻才拐,这样非方形矩阵也不会算错。

写入 4 到 (1,3)：把链表当前值 4 写进 (1,3),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 5 个格子。

直行向下 · 走向 (2,3)：站在刚写完的这一格,判断下一步。朝向下探一格,下一格 (2,3) 在界内、而且还是 -1,没填过,直接迈过去。

写入 8 到 (2,3)：把链表当前值 8 写进 (2,3),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 6 个格子。

拐弯 · 转到向左,走向 (2,2)：站在刚写完的这一格,判断下一步。朝向下探一格会走出矩阵,于是顺时针转到向左,探到 (2,2) 在界内又还是 -1,迈过去。注意转向不是数着走了几步才拐,而是探到走不动的那一刻才拐,这样非方形矩阵也不会算错。

写入 2 到 (2,2)：把链表当前值 2 写进 (2,2),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 7 个格子。

直行向左 · 走向 (2,1)：站在刚写完的这一格,判断下一步。朝向左探一格,下一格 (2,1) 在界内、而且还是 -1,没填过,直接迈过去。

写入 6 到 (2,1)：把链表当前值 6 写进 (2,1),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 8 个格子。

链表写完 · 螺旋在半路停下：链表的 8 个值全部写完,侧栏空了。螺旋才走到 (2,1) 就停在了半路,根本没绕回中间。矩阵一共 12 格,只写了 8 格,还剩下 4 格从头到尾没人碰过。这 4 个空格该怎么办,下一步见分晓。

盘点空格 · 中间和左边还空着 4 格：把还显示点的空格挑出来看:(1,0)、(1,1)、(1,2)、(2,0),这 4 个格子链表没走到。它们正好卡在螺旋还没绕进去的中间地带。因为一开始整张矩阵就是 -1,这些格子其实一直安安静静地保持着 -1,我们什么都不用额外做。

剩余空格保留 -1：现在把那 4 个空格的真面目亮出来:它们都是 -1,刷成浅蓝。这一步其实没做任何新动作,只是把「一开始就铺好的 -1」显示出来而已。这正是先整张铺 -1 的妙处:剩余格子天然就是 -1,省得最后再回头补。到此,12 个格子全部有值。

回放 · 最终矩阵成形：回放一遍全程。绿色是链表螺旋填出来的 8 个值:先沿第一行 3、7、1、9 向右,撞墙转下走 4、8,再转左走 2、6,链表就空了。浅蓝的 4 个 -1 是没被螺旋绕到的空位。合起来就是最终答案:第一行 3、7、1、9,第二行 -1、-1、-1、4,第三行 -1、6、2、8。

边界想清:单行就退化成从左往右填、一格矩阵写完即停、链表正好填满时无 -1,这些都被同一套「越界或已填就转向」的判断自动处理。

面试重点:先铺 -1 加螺旋指针、按「界内且仍为 -1」判转向可连转、时间 O(m 乘 n) 额外空间 O(1)。

§3

参考代码

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = next# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass 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

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(m·n)，m 行 n 列共 m 乘 n 个格子。初始化整张矩阵是 m 乘 n;主循环每写一个链表值前进一格,内层找下一格时最多连转几次方向,但每格总的转向次数是常数摊销,整体随格子总数线性
空间：O(1)，按峰值算,只用了 i、j、k 几个下标变量,没有另开访问表。必须返回的结果矩阵是 O(m 乘 n),但那是题目要求的输出、不计入额外空间;真正的辅助空间是常数

§5

易错点

✗ 错误写法：按「走 n 步再拐、走 m-1 步再拐」的层数法数着走

✓ 正确写法：统一判断「下一格越界或已填就转向」

数步数法在链表提前走完、或者行列不等时边界极易写错;按格判断天然处理提前结束和非方形矩阵

✗ 错误写法：Java 里忘了把矩阵初始化成 -1

✓ 正确写法：用 Arrays 的 fill 把每行刷成 -1

Java 的 int 数组默认值是 0,不填就会把没写到的格子留成 0 而不是 -1,直接答案错

✗ 错误写法：转一次向就以为新方向一定能走

✓ 正确写法：转向后要重新判断,必要时连续转

走到角落时可能一次转向后新方向也越界或已填,得靠 k 加一取模的循环一直转到找着合法格为止

✗ 错误写法：另开一张 visited 表记录哪格填过

✓ 正确写法：直接看那格是不是还等于 -1

题目节点值都在 0 到 1000、非负,-1 不可能是真实值,用它当未填标记既省一张表又不会误判

面试追问把动画讲成自己的话

追问这题的核心思路一句话怎么说?

把整张矩阵先铺成 -1,一个指针从左上角沿右下左上顺时针螺旋走,每格写下链表当前值。走下一步前先探当前方向的下一格,若越界或已填过就顺时针转向,直到探到界内且仍为 -1 的格子。链表走完就停,没写到的格子自然留着 -1。

追问怎么判断该转向,又怎么保证转向后还合法?

判断依据是下一格是否「在界内且还等于 -1」。用一个方向下标 k 配上方向数组取偏移;探到走不动就 k 加一对 4 取模换下个方向,并且是放在一个内层循环里一直转,直到找着能落脚的格子,所以哪怕在角落连续越界也能连转好几次转到位。

追问复杂度是多少,空间能不能做到常数?

时间 O(m 乘 n),每个格子被写入一次,转向的总次数是常数摊销。额外空间 O(1),只用几个下标变量,靠「格子是否还等于 -1」当未填标记,不用另开访问表;必须返回的结果矩阵是题目要求的输出,不计入额外空间。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 链表套路 41/44

从链表中移除节点

LeetCode 2487 · 中等 · 沿着链表套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass 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

螺旋矩阵 IV

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

从链表中移除节点

把这道题真正学会，再走

螺旋矩阵 IV

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

从链表中移除节点

把这道题真正学会，再走