Medium

题目描述

给你两个整数 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 <= 10^5
  • 1 <= m * n <= 10^5
  • 链表中节点数目在范围 [1, m * n] 内
  • 0 <= Node.val <= 1000

解题思路

解题思路

这是一个模拟螺旋填充的经典问题，结合了链表遍历。

核心思路：

  1. 创建一个 m × n 的矩阵，初始化为 -1
  2. 使用方向向量控制螺旋方向：右→下→左→上，循环往复
  3. 维护当前位置和当前方向，按螺旋顺序填充链表值
  4. 当遇到边界或已填充位置时，顺时针旋转方向

具体实现：

  • 方向向量：[(0,1), (1,0), (0,-1), (-1,0)] 分别表示右、下、左、上
  • 边界判断：检查是否越界或位置已被填充（不为-1）
  • 方向切换：当无法继续前进时，将方向索引 (dir + 1) % 4

时间复杂度分析：

  • 最多访问矩阵中每个位置一次：O(m×n)
  • 链表遍历：O(链表长度)
  • 总体：O(m×n)

空间复杂度：

  • 矩阵存储：O(m×n)
  • 其他辅助空间：O(1)

这种方法简洁高效，利用方向向量优雅地处理了螺旋遍历的方向变化问题。

代码实现

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> matrix(m, vector<int>(n, -1));
        
        // 方向向量：右、下、左、上
        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dir = 0; // 当前方向索引
        int row = 0, col = 0; // 当前位置
        
        ListNode* curr = head;
        while (curr) {
            matrix[row][col] = curr->val;
            curr = curr->next;
            
            // 计算下一个位置
            int nextRow = row + directions[dir].first;
            int nextCol = col + directions[dir].second;
            
            // 检查是否需要转向
            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || 
                matrix[nextRow][nextCol] != -1) {
                dir = (dir + 1) % 4; // 顺时针转向
                nextRow = row + directions[dir].first;
                nextCol = col + directions[dir].second;
            }
            
            row = nextRow;
            col = nextCol;
        }
        
        return matrix;
    }
};

class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        matrix = [[-1] * n for _ in range(m)]
        
        # 方向向量：右、下、左、上
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        dir_idx = 0  # 当前方向索引
        row, col = 0, 0  # 当前位置
        
        curr = head
        while curr:
            matrix[row][col] = curr.val
            curr = curr.next
            
            # 计算下一个位置
            next_row = row + directions[dir_idx][0]
            next_col = col + directions[dir_idx][1]
            
            # 检查是否需要转向
            if (next_row < 0 or next_row >= m or next_col < 0 or next_col >= n or 
                matrix[next_row][next_col] != -1):
                dir_idx = (dir_idx + 1) % 4  # 顺时针转向
                next_row = row + directions[dir_idx][0]
                next_col = col + directions[dir_idx][1]
            
            row, col = next_row, next_col
        
        return matrix

public class Solution {
    public int[][] SpiralMatrix(int m, int n, ListNode head) {
        int[][] matrix = new int[m][];
        for (int i = 0; i < m; i++) {
            matrix[i] = new int[n];
            Array.Fill(matrix[i], -1);
        }
        
        // 方向向量：右、下、左、上
        int[,] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dir = 0; // 当前方向索引
        int row = 0, col = 0; // 当前位置
        
        ListNode curr = head;
        while (curr != null) {
            matrix[row][col] = curr.val;
            curr = curr.next;
            
            // 计算下一个位置
            int nextRow = row + directions[dir, 0];
            int nextCol = col + directions[dir, 1];
            
            // 检查是否需要转向
            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || 
                matrix[nextRow][nextCol] != -1) {
                dir = (dir + 1) % 4; // 顺时针转向
                nextRow = row + directions[dir, 0];
                nextCol = col + directions[dir, 1];
            }
            
            row = nextRow;
            col = nextCol;
        }
        
        return matrix;
    }
}

var spiralMatrix = function(m, n, head) {
    const matrix = Array(m).fill().map(() => Array(n).fill(-1));
    
    // 方向向量：右、下、左、上
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let dir = 0; // 当前方向索引
    let row = 0, col = 0; // 当前位置
    
    let curr = head;
    while (curr) {
        matrix[row][col] = curr.val;
        curr = curr.next;
        
        // 计算下一个位置
        let nextRow = row + directions[dir][0];
        let nextCol = col + directions[dir][1];
        
        // 检查是否需要转向
        if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || 
            matrix[nextRow][nextCol] !== -1) {
            dir = (dir + 1) % 4; // 顺时针转向
            nextRow = row + directions[dir][0];
            nextCol = col + directions[dir][1];
        }
        
        row = nextRow;
        col = nextCol;
    }
    
    return matrix;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
整体复杂度O(m × n)O(m × n)

详细分析：

  • 时间复杂度： O(m × n)，需要遍历矩阵中的每个位置最多一次，链表遍历的时间复杂度为 O(链表长度)，总体为 O(m × n)
  • 空间复杂度： O(m × n)，需要创建大小为 m × n 的矩阵，其他辅助空间为 O(1)

相关题目