### Problem Statement

In this problem, we would be given a 2D matrix, and we need to construct a linked list from it.

### Problem Statement Understanding

Let's see what the problem is demanding.

- In this problem, we will be given a 2D matrix, and we just need to establish the link between all the elements of the matrix.
- Considering the elements of the matrix as a node of a linked list, we need to connect a node with its immediate right and down element in the respective matrix.
- If there is no element present to the immediate right or immediate down of an element, then we need to consider the immediate right and down elements as NULL.

Let us try to understand the problem statement with the help of examples.

#### Input

##### 2 6 3

##### 7 1 9

##### 5 4 8

## Output

**Explanation**

- In the above example, all the nodes are connected in the same manner as they are present in the matrix.
- For example, Node
**6**is pointing to two different nodes, i.e., its right pointer points to its immediate right element, which is**3**and its down pointer points to its immediate down element which is**1**. - When there are no nodes present to the immediate right or down of an element, i.e., for boundary elements, it is considered as the end of the list, and they are made to point NULL pointer. For example, as there is no right element of
**9**, so its right pointer is made to point NULL pointer.

#### Input

##### 0 4 8

##### 3 7 2

### Output

Now, I hope from the above examples the problem is clear. So now, let's think about how we can approach this problem?

In the next section, have a look at some helpful observations.

#### Helpful observations

- We need to construct a linked list in which each node will have two pointers named right and down.
- We just need to create a node for each cell of the matrix and then attach it to its right and down elements, respectively.
- Remember to point to a NULL pointer when we reach the boundary of the matrix.

### Approach

- We will first create
**N**(**N**= number of rows) linked lists, where i^{th}linked list will contain all the elements of the i^{th}row of the given matrix. Each node of i^{th}linked list will store the address of its immediate right element from the matrix in its right link. - We will create an array of pointers that will keep track of the address of the first nodes of all
**N**lists that are created in the previous step. - Then, we will traverse all lists one by one, and while traversing for i
^{th}list, we will assign the down pointer of each node to its corresponding immediate down element in (i+1)^{th}list.

### Algorithm

- Create an array of pointers (say
**head**) of size equal to the number of rows in the matrix. - Create a for loop that will traverse through all the matrix rows and inside this for loop initialize the
**head[i]**to NULL. - Create a nested for loop (inner loop of for loop which we created in previous step) to traverse the column elements of the matrix and while traversing create new nodes having value equal to the value at corrsponding position in the original matrix and then, check if
**head[i]**is NULL or not.- If
**head[i]**is NULL, that means we are at the first column, so we need to store the address of the newly created node into this**head[i]**. - If
**head[i]**is not NULL, we will attach this current node in the i^{th}linked list. - Then store the address of this node in the
**righttemp**variable so that we can attach the new node after this node further.

- If
- After the execution of the above nested for loops, we need to loop through the head array again and connect down pointers of the corresponding i
^{th}list to (i+1)^{th}list. - Now return
**head[0]**from the function, as it would contain the address of the first node of the newly created linked list. - After performing the above steps, we would get our desired linked list constructed from the given 2-D matrix.

### Dry Run

### Code Implementation

#includeusing namespace std; class Node { public: int data; Node* right, *down; Node(int x){ data = x; right = NULL; down = NULL; } }; void display(Node* head) { // pointer that will move rightwards Node* Rp; // pointer that will move downwards Node* Dp = head; // iterate till down pointer is not NULL while (Dp) { Rp = Dp; // iterate till right pointer is not NULL while (Rp) { cout << Rp->data << " "; Rp = Rp->right; } cout << "\n"; Dp = Dp->down; } } Node* constructLinkedListMatrix(int mat[][3], int n, int m) { // array to store starting address of each each row Node* head[m]; Node *righttemp, *newptr; // create ânâ linked lists for each row for (int i = 0; i < n; i++) { // initialize head[i] with NULL head[i] = NULL; for (int j = 0; j < m; j++) { // create a new node newptr = new Node(mat[i][j]); // this means that we are in first column so we need // to store the address of first node of each row if (!head[i]) head[i] = newptr; else righttemp->right = newptr;// attach node to its // right node righttemp = newptr; } } // For every ith rowâs list set corresponding down pointers // to (i+1)th listâs node for (int i = 0; i < n - 1; i++) { Node *temp1 = head[i], *temp2 = head[i + 1]; while (temp1 && temp2) { temp1->down = temp2; temp1 = temp1->right; temp2 = temp2->right; } } // return the head[0] pointer as it is the main head pointer // of the newly created list return head[0]; } int main() { // 2D matrix int arr[][3] = { { 2, 6, 3 }, { 7, 1, 9 }, { 5, 4, 8 } }; int row = 3, col = 3; Node* head = constructLinkedListMatrix(arr, row, col); display(head); return 0; }

#### Output

2 6 3

7 1 9

5 4 8

**Time Complexity:** O(n*m), where **n** is the number of rows in the matrix and **m** is the number of columns in the matrix.

So, in this blog, we have tried to explain how you can construct a linked list from a 2-D matrix in the most optimal way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.