/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func next(head *ListNode) (*ListNode, int) {
	if head != nil {
		val := head.Val
		return head.Next, val
	}
	return nil, -1
}

func fillBorder(m1, m2, n1, n2 int, head *ListNode, matrix [][]int) {
	// North
	if n2-n1 < 1 || m2-m1 < 1 {
		return
	}
	for i := n1; i < n2; i++ {
		head, matrix[m1][i] = next(head)
	}

	// East
	if m2-m1 < 1 {
		return
	}
	for j := m1 + 1; j < m2; j++ {
		head, matrix[j][n2-1] = next(head)
	}

	// South
	if n2-n1 <= 1 || m2-m1 <= 1 {
		return
	}
	for i := n2 - 2; i >= n1; i-- {
		head, matrix[m2-1][i] = next(head)
	}

	// West
	if m2-m1 <= 1 {
		return
	}
	for j := m2 - 2; j > m1; j-- {
		head, matrix[j][m1] = next(head)
	}
	fillBorder(m1+1, m2-1, n1+1, n2-1, head, matrix)
}

func spiralMatrix(m int, n int, head *ListNode) [][]int {
	matrix := make([][]int, m)
	for i, _ := range matrix {
		matrix[i] = make([]int, n)
	}

	fillBorder(0, m, 0, n, head, matrix)

	return matrix
}