Construct a linked list from 2D matrix
Last Updated :
01 May, 2023
Given a matrix. Convert it into a linked list matrix such that each node is connected to its next right and down node.
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
Question Source: Factset Interview Experience | Set 9
Approach: The problem can be solved based on the following idea:
Connect every cell to its right cell of the same row and to its bottom cell in the same column and also for each cell and keep track of those created node.
Follow the steps mentioned below to solve this problem:
- First create a variable of Node type, which will store address of its right and bottom Node corresponding to cell in the matrix.
- Recursively do the following steps for any cell in the matrix:
- If Node is not created for any corresponding cell in the matrix, then create a new Node and store it.
- Else we reach at some cell which has already been created for its corresponding cell in the matrix then return that stored Node.
- Attach Node to its right and bottom cell which is created and return the current Node.
- Finally return the root Node.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *right, *down;
};
Node* construct(int arr[][4], int i, int j, int m, int n,
vector<vector<Node*> >& visited)
{
if (i > m - 1 || j > n - 1)
return NULL;
if (visited[i][j]) {
return visited[i][j];
}
Node* temp = new Node();
visited[i][j] = temp;
temp->data = arr[i][j];
temp->right = construct(arr, i, j + 1, m, n, visited);
temp->down = construct(arr, i + 1, j, m, n, visited);
return temp;
}
void display(Node* head)
{
Node* Rp;
Node* Dp = head;
while (Dp) {
Rp = Dp;
while (Rp) {
cout << Rp->data << " ";
Rp = Rp->right;
}
cout << "\n";
Dp = Dp->down;
}
}
int main()
{
int arr[][4] = { { 1, 2, 3, 0 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 2 },
{ 7, 8, 9, 2 } };
int m = 4, n = 4;
vector<vector<Node*> > visited(m, vector<Node*>(n));
Node* head = construct(arr, 0, 0, m, n, visited);
display(head);
return 0;
}
|
Java
public class Linked_list_2D_Matrix {
static class Node {
int data;
Node right;
Node down;
};
static Node construct(int arr[][], int i, int j, int m,
int n, Node[][] visited)
{
if (i > m - 1 || j > n - 1)
return null;
if (visited[i][j] != null) {
return visited[i][j];
}
Node temp = new Node();
visited[i][j] = temp;
temp.data = arr[i][j];
temp.right
= construct(arr, i, j + 1, m, n, visited);
temp.down = construct(arr, i + 1, j, m, n, visited);
return temp;
}
static void display(Node head)
{
Node Rp;
Node Dp = head;
while (Dp != null) {
Rp = Dp;
while (Rp != null) {
System.out.print(Rp.data + " ");
Rp = Rp.right;
}
System.out.println();
Dp = Dp.down;
}
}
public static void main(String args[])
{
int arr[][] = { { 1, 2, 3, 0 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 2 },
{ 7, 8, 9, 2 } };
int m = 4, n = 4;
Node[][] visited = new Node[m][n];
Node head = construct(arr, 0, 0, m, n, visited);
display(head);
}
}
|
Python3
class Node:
def __init__(self, data=None, right=None, down=None):
self.data = data
self.right = right
self.down = down
def construct(arr, i, j, m, n, visited):
if i > m - 1 or j > n - 1:
return None
if visited[i][j]:
return visited[i][j]
node = Node(arr[i][j])
visited[i][j] = node
node.right = construct(arr, i, j + 1, m, n, visited)
node.down = construct(arr, i + 1, j, m, n, visited)
return node
def display(head):
Rp = head
Dp = head
while Dp:
Rp = Dp
while Rp:
print(Rp.data, end=" ")
Rp = Rp.right
print()
Dp = Dp.down
if __name__ == "__main__":
arr = [[1, 2, 3, 0],
[4, 5, 6, 1],
[7, 8, 9, 2],
[7, 8, 9, 2]]
m = 4
n = 4
visited = [[None] * n for _ in range(m)]
head = construct(arr, 0, 0, m, n, visited)
display(head)
|
C#
using System;
using System.Collections.Generic;
class Node {
public int data;
public Node right;
public Node down;
}
class Linked_list_2D_Matrix
{
static Node construct(int[, ] arr, int i, int j, int m,
int n, Node[, ] visited)
{
if (i > m - 1 || j > n - 1)
return null;
if (visited[i, j] != null) {
return visited[i, j];
}
Node temp = new Node();
visited[i, j] = temp;
temp.data = arr[i, j];
temp.right
= construct(arr, i, j + 1, m, n, visited);
temp.down = construct(arr, i + 1, j, m, n, visited);
return temp;
}
static void display(Node head)
{
Node Rp;
Node Dp = head;
while (Dp != null) {
Rp = Dp;
while (Rp != null) {
Console.Write(Rp.data + " ");
Rp = Rp.right;
}
Console.WriteLine();
Dp = Dp.down;
}
}
public static void Main(string[] args)
{
int[, ] arr = { { 1, 2, 3, 0 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 2 },
{ 7, 8, 9, 2 } };
int m = 4, n = 4;
Node[, ] visited = new Node[m, n];
Node head = construct(arr, 0, 0, m, n, visited);
display(head);
}
}
|
Javascript
class Node {
constructor() {
this.data;
this.right;
this.down;
}
}
function construct(arr, i, j, m, n, visited) {
if (i > m - 1 || j > n - 1) return null;
if (visited[i][j]) {
return visited[i][j];
}
let temp = new Node();
visited[i][j] = temp;
temp.data = arr[i][j];
temp.right = construct(arr, i, j + 1, m, n, visited);
temp.down = construct(arr, i + 1, j, m, n, visited);
return temp;
}
function display(head) {
let Rp;
let Dp = head;
while (Dp) {
Rp = Dp;
while (Rp) {
console.log(Rp.data + " ");
Rp = Rp.right;
}
Dp = Dp.down;
}
}
var arr = [
[1, 2, 3, 0],
[4, 5, 6, 1],
[7, 8, 9, 2],
[7, 8, 9, 2],
];
let m = 4,
n = 4;
let visited = Array.from(Array(m), () => new Array(n));
var head = construct(arr, 0, 0, m, n, visited);
display(head);
|
Output
1 2 3 0
4 5 6 1
7 8 9 2
7 8 9 2
Time complexity: O(N*M), where N is the number of row and M is the number of column.
Auxiliary space: O(N*M)
Use a pre-allocated array of nodes instead of allocating new nodes:
This will reduce the overhead of dynamic memory allocation and deallocation, which can be significant in some cases. The nodeCounter variable keeps track of the next available node in the array. A sentinel node is used to simplify the linked list construction logic, and eliminates the need for special cases when creating the first node.
Here is an example implementation that incorporates these optimizations:
C++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
struct Node
{
int data;
Node *next;
};
Node nodes[MAXN];
int nodeCounter = 0;
Node *constructLinkedList(int matrix[][4], int rows, int columns)
{
Node *sentinel = &nodes[nodeCounter++];
sentinel->next = NULL;
Node *current = sentinel;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
Node *newNode = &nodes[nodeCounter++];
newNode->data = matrix[i][j];
newNode->next = NULL;
current->next = newNode;
current = current->next;
}
}
return sentinel->next;
}
void printLinkedList(Node *head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main()
{
int matrix[3][4] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}};
Node *head = constructLinkedList(matrix, 3, 4);
printLinkedList(head);
return 0;
}
|
Java
import java.util.*;
class Node {
public int data;
public Node next;
}
class LinkedListFromMatrix {
static Node constructLinkedList(int[][] matrix,
int rows, int columns)
{
Node sentinel = new Node();
sentinel.next = null;
Node current = sentinel;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
Node newNode = new Node();
newNode.data = matrix[i][j];
newNode.next = null;
current.next = newNode;
current = current.next;
}
}
return sentinel.next;
}
static void printLinkedList(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println(" ");
}
public static void main(String[] args)
{
int[][] matrix = new int[][] { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
Node head = constructLinkedList(matrix, 3, 4);
printLinkedList(head);
}
}
|
C#
using System;
class Node
{
public int data;
public Node next;
}
class LinkedListFromMatrix
{
static Node ConstructLinkedList(int[,] matrix, int rows, int columns)
{
Node sentinel = new Node();
sentinel.next = null;
Node current = sentinel;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
Node newNode = new Node();
newNode.data = matrix[i, j];
newNode.next = null;
current.next = newNode;
current = current.next;
}
}
return sentinel.next;
}
static void PrintLinkedList(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine(" ");
}
static void Main(string[] args)
{
int[,] matrix = new int[3, 4] {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}};
Node head = ConstructLinkedList(matrix, 3, 4);
PrintLinkedList(head);
}
}
|
Python3
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def construct_linked_list(matrix):
sentinel = Node()
current = sentinel
for row in matrix:
for element in row:
new_node = Node(element)
current.next = new_node
current = current.next
return sentinel.next
def print_linked_list(head):
while head is not None:
print(head.data, end=" ")
head = head.next
print()
if __name__ == "__main__":
matrix = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]]
head = construct_linked_list(matrix)
print_linked_list(head)
|
Javascript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function constructLinkedList(matrix) {
const sentinel = new Node();
let current = sentinel;
for (const row of matrix) {
for (const element of row) {
const newNode = new Node(element);
current.next = newNode;
current = current.next;
}
}
return sentinel.next;
}
function printLinkedList(head) {
let currentNode = head;
let temp = []
while (currentNode !== null) {
temp.push(currentNode.data);
currentNode = currentNode.next;
}
console.log(temp.join(' '));
}
const matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
];
const head = constructLinkedList(matrix);
printLinkedList(head);
|
Output
1 2 3 4 5 6 7 8 9 10 11 12
Time complexity: O(N*M)
Auxiliary space: O(N*M)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...