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 <bits/stdc++.h> 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[][3], 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[][3] = { { 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.
leave a comment
1 Comments