Given a 2-D matrix. You need to convert it into a linked list matrix s

1.	Given a 2-D matrix. You need to convert it into a linked list matrix such that each node is linked to its next right and down node and display it.
Answer» The idea is to create a new node for each ELEMENT of the matrix and then create its next down and right nodes in a recursive manner. Implementation: Node* construct(int A[][3], int m, int n, int i, int j){ // check if i or j is out of bounds if (i &GT; n - 1 \|\| j > m - 1) return NULL; // a new node for current i and j is created // and its down and right pointers are //recursively allocated Node* t = new Node(); t->value = A[i][j]; t->right = construct(A, m, n, i, j + 1); t->down = construct(A, m, n, i + 1, j); return t;}// FUNCTION to display linked list datavoid printData(Node* head){ // POINTER to MOVE down Node* d; // pointer to move down Node* r; // loop till node->down is not NULL for( d = head; d!=NULL; d = d->down) { for( r = d; r!=NULL; r = r->right) { // loop till node->right is not NULL cout << r->value << " "; } cout << endl; }} Time Complexity: O(m * n) Space Complexity: O(1), ignoring the space required for the final answer.

Given a 2-D matrix. You need to convert it into a linked list matrix such that each node is linked to its next right and down node and display it.

Answer»

The idea is to create a new node for each ELEMENT of the matrix and then create its next down and right nodes in a recursive manner.

Implementation:

Node* construct(int A[][3], int m, int n, int i, int j){ // check if i or j is out of bounds if (i &GT; n - 1 || j > m - 1) return NULL; // a new node for current i and j is created // and its down and right pointers are //recursively allocated Node* t = new Node(); t->value = A[i][j]; t->right = construct(A, m, n, i, j + 1); t->down = construct(A, m, n, i + 1, j); return t;}// FUNCTION to display linked list datavoid printData(Node* head){ // POINTER to MOVE down Node* d; // pointer to move down Node* r; // loop till node->down is not NULL for( d = head; d!=NULL; d = d->down) { for( r = d; r!=NULL; r = r->right) { // loop till node->right is not NULL cout << r->value << " "; } cout << endl; }}

Time Complexity: O(m * n)
Space Complexity: O(1), ignoring the space required for the final answer.

Given a 2-D matrix. You need to convert it into a linked list matrix such that each node is linked to its next right and down node and display it.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment