Construya una lista enlazada a partir de una array 2D – Part 1

Dada una array. Conviértalo en una array de lista enlazada de modo que cada Node esté conectado a su siguiente Node derecho e inferior.

Entrada: array 2D 
1 2 3
4 5 6
7 8 9
Salida:
1 -> 2 -> 3 -> NULL
| | |
v v v
4 -> 5 -> 6 -> NULO
| | |
v v v
7 -> 8 -> 9 -> NULO
| | |
v v v
NULO NULO NULO

Fuente de la pregunta: experiencia de entrevista de Factset | conjunto 9

Planteamiento: El problema se puede resolver a partir de la siguiente idea:

Conecte cada celda a su celda derecha de la misma fila y a su celda inferior en la misma columna y también para cada celda y realice un seguimiento de los Nodes creados. 

Siga los pasos que se mencionan a continuación para resolver este problema:

• Primero cree una variable de tipo Node , que almacenará la dirección de su Node derecho e inferior correspondiente a la celda en la array.
• Realice recursivamente los siguientes pasos para cualquier celda de la array:
  • Si no se crea un Node para ninguna celda correspondiente en la array, cree un nuevo Node y guárdelo .
  • De lo contrario, llegamos a alguna celda que ya se ha creado para su celda correspondiente en la array y luego devolvemos ese Node almacenado.
  • Adjunte Node a su celda derecha e inferior que se crea y devuelva el Node actual.
• Finalmente devuelva el Node raíz .

A continuación se muestra la implementación del enfoque anterior:

// 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[][4], int i, int j,
int m, int n, vector<vector<Node*>> &visited)
{
// return if i or j is out of bounds
if (i > m - 1 || j > n - 1)
return NULL;
// Check if node is previously created then,
// don't need to create new/
if(visited[i][j]){
return visited[i][j];
} 
// create a new node for current i and j
// and recursively allocate its down and
// right pointers
Node* temp = new Node();
visited[i][j] = temp;
temp->data = arr[i][j];
temp->right = construct(arr, i, j + 1, m, n, visited);
temp->down = construct(arr, i + 1, j, m, n, visited);
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 << "\n";
Dp = Dp->down;
}
}
// driver program
int main()
{
// 2D matrix
int arr[][4] = {
{ 1, 2, 3, 0},
{ 4, 5, 6 , 1},
{ 7, 8, 9 , 2},
{ 7, 8, 9 , 2}
};
int m = 4, n = 4;
vector<vector<Node*>> visited(m, vector<Node*>(n));
Node* head = construct(arr, 0, 0, m, n, visited);
display(head);
return 0;
}

// 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, Node[][] visited) {
// return if i or j is out of bounds
if (i > m - 1 || j > n - 1)
return null;
// Check if node is previously created then,
// don't need to create new/
if(visited[i][j] != null){
return visited[i][j];
} 
// create a new node for current i and j
// and recursively allocate its down and
// right pointers
Node temp = new Node();
visited[i][j] = temp;
temp.data = arr[i][j];
temp.right = construct(arr, i, j + 1, m, n, visited);
temp.down = construct(arr, i + 1, j, m, n, visited);
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, 0},
{ 4, 5, 6 , 1},
{ 7, 8, 9 , 2},
{ 7, 8, 9 , 2}
};
int m = 4, n = 4;
// List<List<Node>> arr = new ArrayList<List<Node>>();
Node[][] visited = new Node[m][n];
Node head = construct(arr, 0, 0, m, n, visited);
display(head);
}
}
// This code is contributed by Sumit Ghosh

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

Complejidad temporal: O(N*M) , donde N es el número de fila y M es el número de columna.
Espacio auxiliar: O(N*M)

Este artículo es una contribución de Mandeep Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.