Dado un número K , la tarea es crear la estructura de lista circular enlazada con cuatro punteros que son siguiente, anterior, arriba y abajo usando recursividad.
Nota : No se le permite usar ningún arreglo de punteros o array 2D
Vea este ejemplo para K = 3
Ejemplos:
Input: k = 3
Output: 1 2 3
4 5 6
7 8 9
Explanation:
The structure will look like below
Enfoque:
Siga el siguiente procedimiento paso a paso:
- Primero cree la lista K individualmente conectada con el puntero derecho
- El primer Node de cada lista debe apuntar a su Node inferior a través del puntero hacia abajo
- Ahora, combine la lista K individualmente con el puntero hacia abajo en la fila
- Luego crea el bucle en la lista en filas y columnas
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to recursively create
// loopy linked list with four
// pointer left, right, up, down
// by given value K without using
// array of pointer and 2D matrix
#include <iostream>
using namespace std;
// Struct node of Circular linked
// list with four pointer
// next, prev, up, down
struct Node {
int data;
Node* left;
Node* right;
Node* up;
Node* down;
};
// Function to create a new node
Node* createNode(int value)
{
Node* temp = new Node();
temp->data = value;
temp->left = NULL;
temp->right = NULL;
temp->up = NULL;
temp->down = NULL;
return temp;
}
// Function to create Singly list
// whose nodes are connected with
// right pointer
Node* createListWithRightPointer(int k,
int i)
{
if (i > k)
return NULL;
Node* node = createNode(i);
// Recursively call the function to
// create list with the right pointer
node->right =
createListWithRightPointer(k,
i + 1);
return node;
}
// Function to create the k singly
// linked list and first node of
// each list is connected with
// down pointer
Node* createKsinglyLinkedList(int k)
{
int rNum = 1;
int limit = k;
Node* head = NULL;
Node* rowPointer = NULL;
// Loop to create the k singly list
// for each list first node points
// to its below node by down pointer
for (int i = 1; i <= k; i++) {
Node* templist =
createListWithRightPointer(limit,
rNum);
if (head == NULL) {
head = templist;
rowPointer = head;
}
else {
rowPointer->down = templist;
rowPointer = rowPointer->down;
}
rNum = rNum + k;
limit = limit + k;
}
return head;
}
// Function to merge all list with
// level wise via down pointer
void mergeKListWithDownPointer(Node* head)
{
Node* first = NULL;
Node* second = NULL;
Node* start = head;
first = start;
second = first->down;
// Run while loop to merge k list
// row wise with down pointer
while (second) {
while (first || second) {
first->down = second;
first = first->right;
second = second->right;
}
first = start->down;
second = first->down;
start = start->down;
}
}
// Function to create the loop
// for each column
void createLoopForEachColumn(Node* head)
{
Node* first = NULL;
Node* last = NULL;
first = head;
last = first;
while (last->down) {
last = last->down;
}
// Run while loop to create
// loop for each column
while (first || last) {
last->down = first;
first = first->right;
last = last->right;
}
}
// Function to create the loop
// for each row
void createLoopForEachRow(Node* head)
{
Node* first = NULL;
Node* last = NULL;
Node* start = NULL;
start = head;
first = head;
last = first;
while (last->right) {
last = last->right;
}
// Run while loop to create
// loop for each row
while (first->down != start) {
last->right = first;
first = first->down;
last = last->down;
}
last->right = first;
}
// Function to display the structure
// of the list
void display(Node* head)
{
// Pointer to move right
Node* rPtr;
// Pointer to move down
Node* dPtr = head;
// Pointer to stop printing
Node* start = head;
// Loop till node->down is not NULL
while (dPtr->down != start) {
rPtr = dPtr;
// Loop till node->right is
// not NULL
while (rPtr->right != dPtr) {
cout << rPtr->data << " ";
rPtr = rPtr->right;
}
cout << rPtr->data << " ";
cout << "\n";
dPtr = dPtr->down;
}
rPtr = dPtr;
// Loop till node->right is
// not NULL
while (rPtr->right != dPtr) {
cout << rPtr->data << " ";
rPtr = rPtr->right;
}
cout << rPtr->data << " ";
cout << "\n";
}
void createLoopInList(int k)
{
// Create k singly Linked List each
// first node of all list contain
// address of it's below first node
Node* head = createKsinglyLinkedList(k);
mergeKListWithDownPointer(head);
createLoopForEachColoumn(head);
createLoopForEachRow(head);
display(head);
}
int main()
{
int K = 4;
// Create the list structure
createLoopInList(K);
}
Java
// Java program to recursively create
// loopy linked list with four
// pointer left, right, up, down
// by given value K without using
// array of pointer and 2D matrix
class GFG{
// Struct node of Circular linked
// list with four pointer
// next, prev, up, down
static class Node {
int data;
Node left;
Node right;
Node up;
Node down;
};
// Function to create a new node
static Node createNode(int value)
{
Node temp = new Node();
temp.data = value;
temp.left = null;
temp.right = null;
temp.up = null;
temp.down = null;
return temp;
}
// Function to create Singly list
// whose nodes are connected with
// right pointer
static Node createListWithRightPointer(int k,
int i)
{
if (i > k)
return null;
Node node = createNode(i);
// Recursively call the function to
// create list with the right pointer
node.right =
createListWithRightPointer(k,
i + 1);
return node;
}
// Function to create the k singly
// linked list and first node of
// each list is connected with
// down pointer
static Node createKsinglyLinkedList(int k)
{
int rNum = 1;
int limit = k;
Node head = null;
Node rowPointer = null;
// Loop to create the k singly list
// for each list first node points
// to its below node by down pointer
for (int i = 1; i <= k; i++) {
Node templist =
createListWithRightPointer(limit,
rNum);
if (head == null) {
head = templist;
rowPointer = head;
}
else {
rowPointer.down = templist;
rowPointer = rowPointer.down;
}
rNum = rNum + k;
limit = limit + k;
}
return head;
}
// Function to merge all list with
// level wise via down pointer
static void mergeKListWithDownPointer(Node head)
{
Node first = null;
Node second = null;
Node start = head;
first = start;
second = first.down;
// Run while loop to merge k list
// row wise with down pointer
while (second!=null) {
while (first!=null || second!=null) {
first.down = second;
first = first.right;
second = second.right;
}
first = start.down;
second = first.down;
start = start.down;
}
}
// Function to create the loop
// for each column
static void createLoopForEachColumn(Node head)
{
Node first = null;
Node last = null;
first = head;
last = first;
while (last.down!=null) {
last = last.down;
}
// Run while loop to create
// loop for each column
while (first!=null || last!=null) {
last.down = first;
first = first.right;
last = last.right;
}
}
// Function to create the loop
// for each row
static void createLoopForEachRow(Node head)
{
Node first = null;
Node last = null;
Node start = null;
start = head;
first = head;
last = first;
while (last.right!=null) {
last = last.right;
}
// Run while loop to create
// loop for each row
while (first.down != start) {
last.right = first;
first = first.down;
last = last.down;
}
last.right = first;
}
// Function to display the structure
// of the list
static void display(Node head)
{
// Pointer to move right
Node rPtr;
// Pointer to move down
Node dPtr = head;
// Pointer to stop printing
Node start = head;
// Loop till node.down is not null
while (dPtr.down != start) {
rPtr = dPtr;
// Loop till node.right is
// not null
while (rPtr.right != dPtr) {
System.out.print(rPtr.data+ " ");
rPtr = rPtr.right;
}
System.out.print(rPtr.data+ " ");
System.out.print("\n");
dPtr = dPtr.down;
}
rPtr = dPtr;
// Loop till node.right is
// not null
while (rPtr.right != dPtr) {
System.out.print(rPtr.data+ " ");
rPtr = rPtr.right;
}
System.out.print(rPtr.data+ " ");
System.out.print("\n");
}
static void createLoopInList(int k)
{
// Create k singly Linked List each
// first node of all list contain
// address of it's below first node
Node head = createKsinglyLinkedList(k);
mergeKListWithDownPointer(head);
createLoopForEachColoumn(head);
createLoopForEachRow(head);
display(head);
}
public static void main(String[] args)
{
int K = 4;
// Create the list structure
createLoopInList(K);
}
}
// This code contributed by sapnasingh4991
Python3
# Python3 program to recursively create # loopy linked list with four # pointer left, right, up, down # by given value K without using # array of pointer and 2D matrix # Struct node of Circular linked # list with four pointer # next, prev, up, down class Node: def __init__(self, data): self.left = None self.right = None self.up = None self.down = None self.data = data # Function to create a new node def createNode(value): temp = Node(value) return temp; # Function to create Singly list # whose nodes are connected with # right pointer def createListWithRightPointer(k, i): if (i > k): return None; node = createNode(i); # Recursively call the function to # create list with the right pointer node.right = createListWithRightPointer(k, i + 1); return node; # Function to create the k singly # linked list and first node of # each list is connected with # down pointer def createKsinglyLinkedList( k): rNum = 1; limit = k; head = None; rowPointer = None; # Loop to create the k singly list # for each list first node points # to its below node by down pointer for i in range(1, k + 1): templist = createListWithRightPointer(limit, rNum); if (head == None): head = templist; rowPointer = head; else: rowPointer.down = templist; rowPointer = rowPointer.down; rNum = rNum + k; limit = limit + k; return head; # Function to merge all list with # level wise via down pointer def mergeKListWithDownPointer(head): first = None; second = None; start = head; first = start; second = first.down; # Run while loop to merge k list # row wise with down pointer while (second): while (first or second): first.down = second; first = first.right; second = second.right; first = start.down; second = first.down; start = start.down; # Function to create the loop # for each column def createLoopForEachColumn(head): first = None; last = None; first = head; last = first; while (last.down): last = last.down; # Run while loop to create # loop for each column while (first or last): last.down = first; first = first.right; last = last.right; # Function to create the loop # for each row def createLoopForEachRow(head): first = None; last = None; start = None; start = head; first = head; last = first; while (last.right): last = last.right; # Run while loop to create # loop for each row while (first.down != start): last.right = first; first = first.down; last = last.down; last.right = first; # Function to display the structure # of the list def display(head): # Pointer to move right rPtr = None # Pointer to move down dPtr = head; # Pointer to stop printing start = head; # Loop till node.down is not None while (dPtr.down != start): rPtr = dPtr; # Loop till node.right is # not None while (rPtr.right != dPtr): print(rPtr.data, end = ' ') rPtr = rPtr.right; print(rPtr.data) dPtr = dPtr.down; rPtr = dPtr; # Loop till node.right is # not None while (rPtr.right != dPtr): print(rPtr.data, end=' ') rPtr = rPtr.right; print(rPtr.data) def createLoopInList( k): # Create k singly Linked List each # first node of all list contain # address of it's below first node head = createKsinglyLinkedList(k); mergeKListWithDownPointer(head); createLoopForEachColoumn(head); createLoopForEachRow(head); display(head); # Diver code if __name__=='__main__': K = 4; # Create the list structure createLoopInList(K); # This code is contributed by rutvik_56
C#
// C# program to recursively create
// loopy linked list with four
// pointer left, right, up, down
// by given value K without using
// array of pointer and 2D matrix
using System;
class GFG{
// Struct node of circular linked
// list with four pointer
// next, prev, up, down
class Node
{
public int data;
public Node left;
public Node right;
public Node up;
public Node down;
};
// Function to create a new node
static Node createNode(int value)
{
Node temp = new Node();
temp.data = value;
temp.left = null;
temp.right = null;
temp.up = null;
temp.down = null;
return temp;
}
// Function to create Singly list
// whose nodes are connected with
// right pointer
static Node createListWithRightPointer(int k,
int i)
{
if (i > k)
return null;
Node node = createNode(i);
// Recursively call the function to
// create list with the right pointer
node.right = createListWithRightPointer(k,
i + 1);
return node;
}
// Function to create the k singly
// linked list and first node of
// each list is connected with
// down pointer
static Node createKsinglyList(int k)
{
int rNum = 1;
int limit = k;
Node head = null;
Node rowPointer = null;
// Loop to create the k singly list
// for each list first node points
// to its below node by down pointer
for(int i = 1; i <= k; i++)
{
Node templist =createListWithRightPointer(limit,
rNum);
if (head == null)
{
head = templist;
rowPointer = head;
}
else
{
rowPointer.down = templist;
rowPointer = rowPointer.down;
}
rNum = rNum + k;
limit = limit + k;
}
return head;
}
// Function to merge all list with
// level wise via down pointer
static void mergeKListWithDownPointer(Node head)
{
Node first = null;
Node second = null;
Node start = head;
first = start;
second = first.down;
// Run while loop to merge k list
// row wise with down pointer
while (second != null)
{
while (first != null || second != null)
{
first.down = second;
first = first.right;
second = second.right;
}
first = start.down;
second = first.down;
start = start.down;
}
}
// Function to create the loop
// for each column
static void createLoopForEachColumn(Node head)
{
Node first = null;
Node last = null;
first = head;
last = first;
while (last.down != null)
{
last = last.down;
}
// Run while loop to create
// loop for each column
while (first != null || last != null)
{
last.down = first;
first = first.right;
last = last.right;
}
}
// Function to create the loop
// for each row
static void createLoopForEachRow(Node head)
{
Node first = null;
Node last = null;
Node start = null;
start = head;
first = head;
last = first;
while (last.right != null)
{
last = last.right;
}
// Run while loop to create
// loop for each row
while (first.down != start)
{
last.right = first;
first = first.down;
last = last.down;
}
last.right = first;
}
// Function to display the structure
// of the list
static void display(Node head)
{
// Pointer to move right
Node rPtr;
// Pointer to move down
Node dPtr = head;
// Pointer to stop printing
Node start = head;
// Loop till node.down is not null
while (dPtr.down != start)
{
rPtr = dPtr;
// Loop till node.right is
// not null
while (rPtr.right != dPtr)
{
Console.Write(rPtr.data + " ");
rPtr = rPtr.right;
}
Console.Write(rPtr.data + " ");
Console.Write("\n");
dPtr = dPtr.down;
}
rPtr = dPtr;
// Loop till node.right is
// not null
while (rPtr.right != dPtr)
{
Console.Write(rPtr.data + " ");
rPtr = rPtr.right;
}
Console.Write(rPtr.data + " ");
Console.Write("\n");
}
static void createLoopInList(int k)
{
// Create k singly Linked List each
// first node of all list contain
// address of it's below first node
Node head = createKsinglyList(k);
mergeKListWithDownPointer(head);
createLoopForEachColoumn(head);
createLoopForEachRow(head);
display(head);
}
// Driver code
public static void Main(String[] args)
{
int K = 4;
// Create the list structure
createLoopInList(K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to recursively create
// loopy linked list with four
// pointer left, right, up, down
// by given value K without using
// array of pointer and 2D matrix
// Struct node of Circular linked
// list with four pointer
// next, prev, up, down
class Node {
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
this.up = null;
this.down = null;
}
};
// Function to create a new node
function createNode(value)
{
var temp = new Node();
temp.data = value;
temp.left = null;
temp.right = null;
temp.up = null;
temp.down = null;
return temp;
}
// Function to create Singly list
// whose nodes are connected with
// right pointer
function createListWithRightPointer(k, i)
{
if (i > k)
return null;
var node = createNode(i);
// Recursively call the function to
// create list with the right pointer
node.right =
createListWithRightPointer(k,
i + 1);
return node;
}
// Function to create the k singly
// linked list and first node of
// each list is connected with
// down pointer
function createKsinglyLinkedList(k)
{
var rNum = 1;
var limit = k;
var head = null;
var rowPointer = null;
// Loop to create the k singly list
// for each list first node points
// to its below node by down pointer
for (var i = 1; i <= k; i++) {
var templist =
createListWithRightPointer(limit,
rNum);
if (head == null) {
head = templist;
rowPointer = head;
}
else {
rowPointer.down = templist;
rowPointer = rowPointer.down;
}
rNum = rNum + k;
limit = limit + k;
}
return head;
}
// Function to merge all list with
// level wise via down pointer
function mergeKListWithDownPointer(head)
{
var first = null;
var second = null;
var start = head;
first = start;
second = first.down;
// Run while loop to merge k list
// row wise with down pointer
while (second) {
while (first || second) {
first.down = second;
first = first.right;
second = second.right;
}
first = start.down;
second = first.down;
start = start.down;
}
}
// Function to create the loop
// for each column
function createLoopForEachColoumn(head)
{
var first = null;
var last = null;
first = head;
last = first;
while (last.down) {
last = last.down;
}
// Run while loop to create
// loop for each column
while (first || last) {
last.down = first;
first = first.right;
last = last.right;
}
}
// Function to create the loop
// for each row
function createLoopForEachRow(head)
{
var first = null;
var last = null;
var start = null;
start = head;
first = head;
last = first;
while (last.right) {
last = last.right;
}
// Run while loop to create
// loop for each row
while (first.down != start) {
last.right = first;
first = first.down;
last = last.down;
}
last.right = first;
}
// Function to display the structure
// of the list
function display(head)
{
// Pointer to move right
var rPtr;
// Pointer to move down
var dPtr = head;
// Pointer to stop printing
var start = head;
// Loop till node.down is not null
while (dPtr.down != start) {
rPtr = dPtr;
// Loop till node.right is
// not null
while (rPtr.right != dPtr) {
document.write( rPtr.data + " ");
rPtr = rPtr.right;
}
document.write( rPtr.data + " ");
document.write( "<br>");
dPtr = dPtr.down;
}
rPtr = dPtr;
// Loop till node.right is
// not null
while (rPtr.right != dPtr) {
document.write( rPtr.data + " ");
rPtr = rPtr.right;
}
document.write( rPtr.data + " ");
document.write("<br>");
}
function createLoopInList(k)
{
// Create k singly Linked List each
// first node of all list contain
// address of it's below first node
var head = createKsinglyLinkedList(k);
mergeKListWithDownPointer(head);
createLoopForEachColoumn(head);
createLoopForEachRow(head);
display(head);
}
var K = 4;
// Create the list structure
createLoopInList(K);
// This code is contributed by noob2000.
</script>
Producción:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA