Create a Circular List Structure For Given Value K Using Recursion
Given a number K, the task is to create the circular linked list structure with four pointers that are next, previous, up, and down Using Recursion.
Note: You are not allowed to use any array of pointers or 2D matrix
See this example for K = 3
Examples:
Input: k = 3 Output: 1 2 3 4 5 6 7 8 9 Explanation: The structure will look like below
Approach:
Follow the below procedure step by step:
- First create the K singly list connected with right pointer
- The first node of each list should point to it’s below node via down pointer
- Now, merge K singly list with down pointer row wise
- Then create the loop in list row-wise and column wise
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of circular linked list node 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); createLoopForEachColumn(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); # Driver 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> |
Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Time complexity: The time complexity of this code is O(k^2) as there is a nested loop that iterates through all elements of the matrix
Space Complexity: The space complexity is O(k^2) as a matrix with k^2 elements is created.
Contact Us