Given a Matrix mat of N*N size, the task is to complete the function constructLinkedMatrix(), that constructs a 2D linked list representation of the given matrix.
Input : 2D matrix 
1 2 3
4 5 6
7 8 9
Output :
1 -> 2 -> 3 -> NULL
|    |    |
v    v    v
4 -> 5 -> 6 -> NULL
|    |    |
v    v    v
7 -> 8 -> 9 -> NULL
|    |    |
v    v    v
NULL NULL NULL
Input:
The fuction takes 2 argument as input, first the 2D matrix mat[][] and second an integer variable N, denoting the size of the matrix.
There will be T test cases and for each test case the function will be called separately.
Output:
The function must return the reference pointer to the head of the linked list.
Constraints:
1<=T<=100
1<=N<=150
Example:
Input:
2
3
1 2 3 4 5 6 7 8 9
2
1 2 3 4
Output:
1 2 3 4 5 6 7 8 9
1 2 3 4
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



'''



class Node():

    def __init__(self,x):

        self.data = x

        self.right = None

        self.down=None



'''



def constructLinkedMatrix(mat,  n):

    #your code goes here

Solutions:
def solve(row, col, mat):
	if row >= len(mat) or col >= len(mat[0]):
		return None
	cur = Node(mat[row][col])
	cur.right = solve(row, col + 1, mat)
	cur.down = solve(row + 1, col, mat)
	return cur

def constructLinkedMatrix(mat, n):
	return solve(0, 0, mat)


def constructLinkedMatrix(mat, n):
	lst = []
	for i in range(n):
		x = Node(mat[i][0])
		lst.append(x)
		for j in range(1, len(mat[i])):
			y = Node(mat[i][j])
			x.right = y
			x = y
	for i in range(1, n):
		p1 = lst[i - 1]
		p2 = lst[i]
		while p1:
			p1.down = p2
			p1 = p1.right
			p2 = p2.right
	return lst[0]


def constructLinkedMatrix(mat, n):
	heads = []
	for row in mat:
		start = Node(0)
		head = start
		for i in range(n):
			head.right = Node(row[i])
			head = head.right
		heads.append(start.right)
	start = heads[0]
	for _ in range(n):
		for i in range(n - 1):
			heads[i].down = heads[i + 1]
			heads[i] = heads[i].right
		heads[-1] = heads[-1].right
	return start


def constructLinkedMatrix(mat, n):
	mat[0][0] = Node(mat[0][0])
	for i in range(1, n):
		mat[0][i] = Node(mat[0][i])
		mat[0][i - 1].right = mat[0][i]
	for i in range(1, n):
		for j in range(n):
			if j == 0:
				mat[i][j] = Node(mat[i][j])
				mat[i - 1][j].down = mat[i][j]
			else:
				mat[i][j] = Node(mat[i][j])
				mat[i - 1][j].down = mat[i][j]
				mat[i][j - 1].right = mat[i][j]
	return mat[0][0]


def constructLinkedMatrix(mat, n):
	node_list = [[None for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			new_node = Node(mat[i][j])
			node_list[i][j] = new_node
	for k in range(n):
		for m in range(n):
			if k == n - 1 and m == n - 1:
				node_list[k][m].down = None
				node_list[k][m].right = None
			elif k == n - 1:
				node_list[k][m].down = None
				node_list[k][m].right = node_list[k][m + 1]
			elif m == n - 1:
				node_list[k][m].right = None
				node_list[k][m].down = node_list[k + 1][m]
			else:
				node_list[k][m].right = node_list[k][m + 1]
				node_list[k][m].down = node_list[k + 1][m]
	return node_list[0][0]


def constructLinkedMatrix(mat, N):
	pre = Node(mat[0][0])
	head = Node(0)
	cur = pre
	head.right = cur
	for i in range(N):
		cur = pre
		for j in range(N):
			if j == N - 1:
				cur.right = None
			else:
				cur.right = Node(mat[i][j + 1])
			if i != N - 1:
				cur.down = Node(mat[i + 1][j])
				if j == 0:
					pre = cur.down
			else:
				cur.down = None
			cur = cur.right
	return head.right


def constructLinkedMatrix(mat, n):
	(i, j) = (0, 0)
	return matrix(mat, n, i, j)

def matrix(mat, n, i, j):
	if i >= n or j >= n:
		return None
	node = Node(mat[i][j])
	node.right = matrix(mat, n, i, j + 1)
	node.down = matrix(mat, n, i + 1, j)
	return node


def recur(m, i, j, n):
	if i >= n or j >= n:
		return None
	if isinstance(m[i][j], Node):
		return m[i][j]
	node = Node(m[i][j])
	node.right = recur(m, i, j + 1, n)
	node.down = recur(m, i + 1, j, n)
	mat[i][j] = node
	return node

def constructLinkedMatrix(mat, n):
	return recur(mat, 0, 0, n)


def constructLinkedMatrix(mat, n):
	list1 = []
	for i in range(n):
		p = None
		headp = None
		count = 0
		for j in range(n):
			if p == None:
				p = Node(mat[i][j])
				headp = p
				if count == 0:
					q = headp
			else:
				p.right = Node(mat[i][j])
				if count == 0:
					q = headp
				p = p.right
			count += 1
		p.down = None
		list1.append(headp)
	length = len(list1)
	i = 0
	while i < length:
		if i == 0:
			n = list1[0]
			m = list1[1]
			head = n
			headm = m
			while n != None and m != None:
				n.down = m
				n = n.right
				m = m.right
			i += 2
		else:
			n = headm
			m = list1[i]
			headm = m
			while n != None and m != None:
				n.down = m
				n = n.right
				m = m.right
			i += 1
	return head


def constructLinkedMatrix(mat, n):
	i = 0
	head = None
	node = None
	pre = None
	while i < n:
		j = 0
		N = Node(mat[j][i])
		nod = N
		pre = N
		if node and j == 0:
			pre = node
			node.right = N
			node = N
			nod = node
		if i == 0 and j == 0:
			node = N
			head = node
		j = 1
		while j < n and pre:
			NN = Node(mat[j][i])
			nod.down = NN
			nod = NN
			pre = pre.down
			if i != 0:
				pre.right = nod
			j += 1
		i += 1
	return head


def constructLinkedMatrix(arr, n):
	for i in range(n):
		for j in range(n):
			arr[i][j] = Node(arr[i][j])
	for i in range(n):
		for j in range(n):
			if j + 1 < n:
				arr[i][j].right = arr[i][j + 1]
			if i + 1 < n:
				arr[i][j].down = arr[i + 1][j]
	return arr[0][0]


def constructLinkedMatrix(mat, n):
	node = Node(mat[0][0])
	head = Node(0)
	cur = node
	head.right = node
	for i in range(n):
		cur = node
		for j in range(n):
			if j == n - 1:
				cur.right = None
			else:
				cur.right = Node(mat[i][j + 1])
			if i != n - 1:
				cur.down = Node(mat[i + 1][j])
				if j == 0:
					node = cur.down
			else:
				cur.down = None
			cur = cur.right
	return head.right


def constructLinkedMatrix(mat, n):
	l = mat.copy()
	for i in range(n):
		for j in range(n):
			l[i][j] = Node(mat[i][j])
	for i in range(n):
		temp = l[i][0]
		j = 1
		while j < n:
			temp.right = l[i][j]
			temp = temp.right
			j += 1
	for i in range(n):
		temp = l[0][i]
		j = 1
		while j < n:
			temp.down = l[j][i]
			temp = temp.down
			j += 1
	return l[0][0]


def constructLinkedMatrix(mat, n):
	for i in range(n):
		for j in range(n):
			mat[i][j] = Node(mat[i][j])
	for i in range(n):
		for j in range(n):
			if i < n - 1 and j < n - 1:
				mat[i][j].right = mat[i][j + 1]
				mat[i][j].down = mat[i + 1][j]
			elif i < n - 1 and j == n - 1:
				mat[i][j].down = mat[i + 1][j]
			elif i == n - 1 and j < n - 1:
				mat[i][j].right = mat[i][j + 1]
	return mat[0][0]


def constructLinkedMatrix(mat, n):
	prev = Node(mat[0][0])
	head = Node(0)
	curr = prev
	head.right = prev
	for i in range(n):
		curr = prev
		for j in range(n):
			if j == n - 1:
				curr.right = None
			else:
				curr.right = Node(mat[i][j + 1])
			if i == n - 1:
				curr.down = None
			else:
				curr.down = Node(mat[i + 1][j])
				if j == 0:
					prev = curr.down
			curr = curr.right
	return head.right


def constructLinkedMatrix(mat, n):
	l = []
	for r in mat:
		d = Node(r.pop(0))
		l.append(d)
		while r:
			d.right = Node(r.pop(0))
			d = d.right
	h = l[0]
	while l[0]:
		for i in range(len(l) - 1):
			l[i].down = l[i + 1]
			if l[i].right:
				l[i] = l[i].right
			else:
				l[i] = None
		if l[-1].right:
			l[-1] = l[-1].right
		else:
			l[-1] = None
	return h

class Node:

	def __init__(self, x):
		self.data = x
		self.right = None
		self.down = None

def display(head):
	Dp = head
	while Dp:
		Rp = Dp
		while Rp:
			print(Rp.data, end=' ')
			if Rp.right:
				print(Rp.right.data, end=' ')
			else:
				print('Null', end=' ')
			if Rp.down:
				print(Rp.down.data, end=' ')
			else:
				print('Null', end=' ')
			Rp = Rp.right
		Dp = Dp.down
if __name__ == '__main__':
	for _ in range(int(input())):
		n = int(input())
		mat = []
		tmp = [int(i) for i in input().split()]
		for i in range(n):
			mat.append(tmp[n * i:n + i * n])
		head = constructLinkedMatrix(mat, n)
		if head == None:
			print(-1)
			continue
		display(head)
		print()


def constructLinkedMatrix(mat, N):
	pre = Node(mat[0][0])
	head = Node(0)
	cur = pre
	head.right = cur
	for i in range(N):
		cur = pre
		for j in range(N):
			if j == N - 1:
				cur.right = None
			else:
				cur.right = Node(mat[i][j + 1])
			if i != N - 1:
				cur.down = Node(mat[i + 1][j])
				if j == 0:
					pre = cur.down
			else:
				cur.down = None
			cur = cur.right
	return head.right

class Node:

	def __init__(self, x):
		self.data = x
		self.right = None
		self.down = None

def display(head):
	Dp = head
	while Dp:
		Rp = Dp
		while Rp:
			print(Rp.data, end=' ')
			if Rp.right:
				print(Rp.right.data, end=' ')
			else:
				print('Null', end=' ')
			if Rp.down:
				print(Rp.down.data, end=' ')
			else:
				print('Null', end=' ')
			Rp = Rp.right
		Dp = Dp.down
if __name__ == '__main__':
	for _ in range(int(input())):
		n = int(input())
		mat = []
		tmp = [int(i) for i in input().split()]
		for i in range(n):
			mat.append(tmp[n * i:n + i * n])
		head = constructLinkedMatrix(mat, n)
		if head == None:
			print(-1)
			continue
		display(head)
		print()


def constructLinkedMatrix(mat, n):
	head = Node(mat[0][0])
	p = head
	for j in range(1, n):
		temp = Node(mat[0][j])
		p.right = temp
		p = p.right
	x = head
	ver = head
	for i in range(1, n):
		rhead = Node(mat[i][0])
		ver.down = rhead
		ver = ver.down
		hor = rhead
		for j in range(1, n):
			x = x.right
			temp = Node(mat[i][j])
			x.down = temp
			hor.right = temp
			hor = hor.right
		x = rhead
	return head


def constructLinkedMatrix(mat, n):
	head = Node(mat[0][0])
	tmp = head
	for i in range(n):
		tmp1 = tmp
		for j in range(n):
			if j == n - 1:
				tmp.right = None
			else:
				tmp.right = Node(mat[i][j + 1])
			if i == n - 1:
				tmp.down = None
			else:
				tmp.down = Node(mat[i + 1][j])
			tmp = tmp.right
		tmp = tmp1
		tmp = tmp.down
	return head


def constructLinkedMatrix(mat, n):
	head = Node(mat[0][0])
	ref = [[None for i in range(n)] for i in range(n)]
	for i in range(n):
		for j in range(n):
			ref[i][j] = Node(mat[i][j])
	for i in range(n - 1):
		for j in range(n - 1):
			ref[i][j].right = ref[i][j + 1]
			ref[i][j].down = ref[i + 1][j]
	for i in range(n - 1):
		ref[n - 1][i].right = ref[n - 1][i + 1]
	for i in range(n - 1):
		ref[i][n - 1].down = ref[i + 1][n - 1]
	return ref[0][0]


def constructLinkedMatrix(mat, n):
	hashMap = {}
	for row in range(len(mat) - 1, -1, -1):
		for col in range(len(mat) - 1, -1, -1):
			newNode = Node(mat[row][col])
			if row == n - 1 and col == n - 1:
				newNode.right = None
				newNode.down = None
			elif col == n - 1:
				newNode.right = None
				newNode.down = hashMap[str(row + 1) + str(col)]
			elif row == n - 1:
				newNode.down = None
				newNode.right = hashMap[str(row) + str(col + 1)]
			elif row != n - 1 and col != n - 1:
				newNode.right = hashMap[str(row) + str(col + 1)]
				newNode.down = hashMap[str(row + 1) + str(col)]
			hashMap[str(row) + str(col)] = newNode
	head = hashMap['00']
	return head


def recur(r, c, i, j, d, a):
	if i >= r or j >= c:
		return None
	if str(i) + '_' + str(j) in d:
		return d[str(i) + '_' + str(j)]
	node = Node(a[i][j])
	node.right = recur(r, c, i, j + 1, d, a)
	node.down = recur(r, c, i + 1, j, d, a)
	d[str(i) + '_' + str(j)] = node
	return node

def constructLinkedMatrix(mat, n):
	d = {}
	i = 0
	j = 0
	r = n
	c = n
	return recur(r, c, i, j, d, mat)


def constructLinkedMatrix(mat, n):
	i = 0
	j = 0
	dp = Node(mat[i][j])
	head = dp
	while i < n:
		rp = dp
		j = 0
		while j < n:
			if j != n - 1:
				rp.right = Node(mat[i][j + 1])
			if i != n - 1:
				rp.down = Node(mat[i + 1][j])
			j += 1
			rp = rp.right
		dp = dp.down
		i += 1
	return head


def make_list(a):
	if a is None or not a:
		return None
	head = Node(a[0])
	tail = head
	for i in range(1, len(a)):
		tail.right = Node(a[i])
		tail = tail.right
	return head

def constructLinkedMatrix(mat, n):
	rows = []
	for r in range(n):
		rows.append(make_list(mat[r]))
	for r in range(n - 1):
		r_curr = rows[r]
		r_next = rows[r + 1]
		t_curr = r_curr
		t_next = r_next
		while t_curr is not None:
			t_curr.down = t_next
			t_curr = t_curr.right
			t_next = t_next.right
	return rows[0]