Convert 2 - D matrix into a linked list

+2 votes
asked in Interview Question by nitin2604

Covert the given 2-D matrix into a linked list, in a such a way that each node is connected with its right and down elements.

For Example:

Matrix Representation : 1    2    3

                                      4    5    6

                                      7    8    9

Linked List Representation ::

                                      1     →    2  →    3 → Null

                                      |              |           |

                                     4      →    5 →     6 → Null

                                       |              |           |

                                     7  →      8  →      9 → Null

                                      |              |           |

                                   Null          Null      Null

 

Add question to:

1 Answer

+2 votes
answered by nitin2604
selected by admin
 
Best answer

Logic:

Since the problem says that each node should be connected with next right element and down element, so I tried with a recursive approach

Make a linked list node structure which has data, right and down elements in it.

struct Node
{
    int data;
    Node* right;
    Node* down;
};

Now for any matrix element follow below steps:
1.Create a new linked list node(llnode) and assign that matrix element to this node(llnode)
2.Call the recursive routine to the left and down nodes of this node like this
    llnode->right = Matrix2LLFun(matrix, rec_row, rec_col + 1, row, col);
    llnode->down = Matrix2LLFun(matrix, rec_row+1, rec_col, row, col);

When you reach the the end of column or row, return NULL.You can check it with below condition

 (rec_row > row - 1 || rec_col > col - 1)

For more clarity see the below code.

Convert 2-D matric into Linked List

#include "iostream"
using namespace std;
//construct the structure
struct Node
{
	int data;
	Node* right;
	Node* down;
};

//this is the recurrsive fucntion of forming linked list from matrix.
Node* Matrix2LLFun(int matrix[3][3], int rec_row, int rec_col, int row, int col){
	if (rec_row > row - 1 || rec_col > col - 1)
		return NULL;
	Node* createNode = new Node; //created a node
	createNode->data = matrix[rec_row][rec_col];
	createNode->right = Matrix2LLFun(matrix, rec_row, rec_col + 1, row, col);
	createNode->down = Matrix2LLFun(matrix, rec_row+1, rec_col, row, col);
	return createNode;
}


int main(){
	int matrix[3][3] = { { 1, 2, 3 },
	{ 4, 5, 6 },
	{ 7, 8, 9 } };
	int row = 3, col = 3;
	Node * head_node = Matrix2LLFun(matrix,0,0,row,col);
	//finally printing out the linked list.
	//now make two pointers one will move row wise and other will move colomn wise.
	Node *row_pointer, *col_pointer;
	row_pointer = head_node;
	while (row_pointer)
	{
		col_pointer = row_pointer;
		while (col_pointer)
		{
			cout << col_pointer->data;
			col_pointer = col_pointer->right;
		}
		cout << endl;
		row_pointer = row_pointer->down;
	}
	return 0;
}

Please comment if there is some problem in understanding the code or logic.

...