# Construct a linked list from 2D matrix

Given a matrix. Convert it into a linked list matrix such that each node is connected to its next right and down node.

Example:

```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

The idea is to construct a new node for every element of matrix and recursively create its down and right nodes.

## C++

 `// CPP program to construct a linked list ` `// from given 2D matrix ` `#include ` `using` `namespace` `std; ` ` `  `// struct node of linked list ` `struct` `Node { ` `    ``int` `data; ` `    ``Node* right, *down; ` `}; ` ` `  `// returns head pointer of linked list ` `// constructed from 2D matrix ` `Node* construct(``int` `arr[], ``int` `i, ``int` `j,  ` `                              ``int` `m, ``int` `n) ` `{ ` `    ``// return if i or j is out of bounds ` `    ``if` `(i > n - 1 || j > m - 1) ` `        ``return` `NULL; ` ` `  `    ``// create a new node for current i and j ` `    ``// and recursively allocate its down and ` `    ``// right pointers ` `    ``Node* temp = ``new` `Node(); ` `    ``temp->data = arr[i][j]; ` `    ``temp->right = construct(arr, i, j + 1, m, n); ` `    ``temp->down  = construct(arr, i + 1, j, m, n); ` `    ``return` `temp; ` `} ` ` `  `// utility function for displaying ` `// linked list data ` `void` `display(Node* head) ` `{ ` `    ``// pointer to move right ` `    ``Node* Rp; ` ` `  `    ``// pointer to move down ` `    ``Node* Dp = head; ` ` `  `    ``// loop till node->down is not NULL ` `    ``while` `(Dp) { ` `        ``Rp = Dp; ` ` `  `        ``// loop till node->right is not NULL ` `        ``while` `(Rp) { ` `            ``cout << Rp->data << ``" "``; ` `            ``Rp = Rp->right; ` `        ``} ` `        ``cout << ````" "````; ` `        ``Dp = Dp->down; ` `    ``} ` `} ` ` `  `// driver program ` `int` `main() ` `{ ` `    ``// 2D matrix ` `    ``int` `arr[] = { ` `        ``{ 1, 2, 3 }, ` `        ``{ 4, 5, 6 }, ` `        ``{ 7, 8, 9 } ` `    ``}; ` ` `  `    ``int` `m = 3, n = 3; ` `    ``Node* head = construct(arr, 0, 0, m, n); ` `    ``display(head); ` `    ``return` `0; ` `} `

## Java

 `// Java program to construct a linked list ` `// from given 2D matrix ` `public` `class` `Linked_list_2D_Matrix { ` ` `  `    ``// node of linked list ` `    ``static` `class` `Node { ` `        ``int` `data; ` `        ``Node right; ` `        ``Node down; ` `    ``}; ` ` `  `    ``// returns head pointer of linked list ` `    ``// constructed from 2D matrix ` `    ``static` `Node construct(``int` `arr[][], ``int` `i, ``int` `j,  ` `                                     ``int` `m, ``int` `n) { ` `         `  `        ``// return if i or j is out of bounds ` `        ``if` `(i > n - ``1` `|| j > m - ``1``) ` `            ``return` `null``; ` ` `  `        ``// create a new node for current i and j ` `        ``// and recursively allocate its down and ` `        ``// right pointers ` `        ``Node temp = ``new` `Node(); ` `        ``temp.data = arr[i][j]; ` `        ``temp.right = construct(arr, i, j + ``1``, m, n); ` `        ``temp.down = construct(arr, i + ``1``, j, m, n); ` `        ``return` `temp; ` `    ``} ` ` `  `    ``// utility function for displaying ` `    ``// linked list data ` `    ``static` `void` `display(Node head) { ` `         `  `        ``// pointer to move right ` `        ``Node Rp; ` ` `  `        ``// pointer to move down ` `        ``Node Dp = head; ` ` `  `        ``// loop till node->down is not NULL ` `        ``while` `(Dp != ``null``) { ` `            ``Rp = Dp; ` ` `  `            ``// loop till node->right is not NULL ` `            ``while` `(Rp != ``null``) { ` `                ``System.out.print(Rp.data + ``" "``); ` `                ``Rp = Rp.right; ` `            ``} ` `            ``System.out.println(); ` `            ``Dp = Dp.down; ` `        ``} ` `    ``} ` ` `  `    ``// driver program ` `    ``public` `static` `void` `main(String args[]) { ` `        ``// 2D matrix ` `        ``int` `arr[][] = { { ``1``, ``2``, ``3` `},  ` `                        ``{ ``4``, ``5``, ``6` `},  ` `                       ``{ ``7``, ``8``, ``9` `} }; ` ` `  `        ``int` `m = ``3``, n = ``3``; ` `        ``Node head = construct(arr, ``0``, ``0``, m, n); ` `        ``display(head); ` `    ``} ` ` `  `} ` `// This code is contributed by Sumit Ghosh `

## C#

 `// C# program to construct a linked list ` `// from given 2D matrix ` `using` `System; ` `     `  `public` `class` `Linked_list_2D_Matrix ` `{ ` ` `  `    ``// node of linked list ` `    ``public` `class` `Node  ` `    ``{ ` `        ``public` `int` `data; ` `        ``public` `Node right; ` `        ``public` `Node down; ` `    ``}; ` ` `  `    ``// returns head pointer of linked list ` `    ``// constructed from 2D matrix ` `    ``static` `Node construct(``int` `[,]arr, ``int` `i, ``int` `j,  ` `                                    ``int` `m, ``int` `n)  ` `    ``{ ` `         `  `        ``// return if i or j is out of bounds ` `        ``if` `(i > n - 1 || j > m - 1) ` `            ``return` `null``; ` ` `  `        ``// create a new node for current i and j ` `        ``// and recursively allocate its down and ` `        ``// right pointers ` `        ``Node temp = ``new` `Node(); ` `        ``temp.data = arr[i, j]; ` `        ``temp.right = construct(arr, i, j + 1, m, n); ` `        ``temp.down = construct(arr, i + 1, j, m, n); ` `        ``return` `temp; ` `    ``} ` ` `  `    ``// utility function for displaying ` `    ``// linked list data ` `    ``static` `void` `display(Node head) ` `    ``{ ` `         `  `        ``// pointer to move right ` `        ``Node Rp; ` ` `  `        ``// pointer to move down ` `        ``Node Dp = head; ` ` `  `        ``// loop till node->down is not NULL ` `        ``while` `(Dp != ``null``)  ` `        ``{ ` `            ``Rp = Dp; ` ` `  `            ``// loop till node->right is not NULL ` `            ``while` `(Rp != ``null``)  ` `            ``{ ` `                ``Console.Write(Rp.data + ``" "``); ` `                ``Rp = Rp.right; ` `            ``} ` `            ``Console.WriteLine(); ` `            ``Dp = Dp.down; ` `        ``} ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``// 2D matrix ` `        ``int` `[,]arr = { { 1, 2, 3 },  ` `                        ``{ 4, 5, 6 },  ` `                    ``{ 7, 8, 9 } }; ` ` `  `        ``int` `m = 3, n = 3; ` `        ``Node head = construct(arr, 0, 0, m, n); ` `        ``display(head); ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

Output:

```1 2 3
4 5 6
7 8 9
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments