Given an array arr[] of integers and a pointer to a random node of a circular sorted linked list (initially empty), the task is to insert all the elements of arr[] into the circular linked list.
Examples:
Input: arr[] = {12, 56, 2, 11, 1, 90}
Output: 1 2 11 12 56 90Input: arr[] = {6, 2, 78, 45, 200}
Output: 2 6 45 78 200
Approach: We are given a random pointer to a node in the circular linked list and we have to find the head of the circular linked list to insert the node in a sorted linked list.
Insertion in a sorted linked list when the head is given is explained in this article.
To find the head of the circular sorted linked list:
- Find the last node of the linked list (the last node will be greater than its successor i.e. first element.
- Once the head of the linked list is found, then the elements can be inserted using the same approach which is discussed in the previous article.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Node structurestruct Node { Node* next; int data;};// Function to create a nodeNode* create(){ Node* new_node = (Node*)malloc(sizeof(Node)); new_node->next = NULL; return new_node;}// Function to find and return the headNode* find_head(Node* random){ // If the list is empty if (random == NULL) return NULL; Node *head, *var = random; // Finding the last node of the linked list // the last node must have the highest value // if no such element is present then all the nodes // of the linked list must be same while (!(var->data > var->next->data || var->next == random)) { var = var->next; } // Return the head return var->next;}// Function to insert a new_node in the list in sorted fashion// Note that this function expects a pointer to head node// as this can modify the head of the input linked listNode* sortedInsert(Node* head_ref, Node* new_node){ Node* current = head_ref; // If the list is empty if (current == NULL) { new_node->next = new_node; head_ref = new_node; } // If the node to be inserted is the smallest // then it has to be the new head else if (current->data >= new_node->data) { // Find the last node of the list as it // will be pointing to the head while (current->next != head_ref) current = current->next; current->next = new_node; new_node->next = head_ref; head_ref = new_node; } else { // Locate the node before the point of insertion while (current->next != head_ref && current->next->data < new_node->data) { current = current->next; } new_node->next = current->next; current->next = new_node; } // Return the new head return head_ref;}// Function to print the nodes of the linked listvoid printList(Node* start){ Node* temp; if (start != NULL) { temp = start; do { cout << temp->data << " "; temp = temp->next; } while (temp != start); }}// Driver codeint main(){ int arr[] = { 12, 56, 2, 11, 1, 90 }; int list_size, i; // Start with an empty linked list Node* start = NULL; Node* temp; // Create linked list from the given array for (i = 0; i < 6; i++) { // Move to a random node if it exists if (start != NULL) for (int j = 0; j < (rand() % 10); j++) start = start->next; temp = create(); temp->data = arr[i]; start = sortedInsert(find_head(start), temp); } // Print the contents of the created list printList(find_head(start)); return 0;} |
Java
// Java implementation of the approachimport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Node structurestatic class Node { Node next; int data;};// Function to create a nodestatic Node create(){ Node new_node = new Node(); new_node.next = null; return new_node;}// Function to find and return the headstatic Node find_head(Node random){ // If the list is empty if (random == null) return null; Node head, var = random; // Finding the last node of the linked list // the last node must have the highest value // if no such element is present then all the nodes // of the linked list must be same while (!(var.data > var.next.data || var.next == random)) { var = var.next; } // Return the head return var.next;}// Function to insert a new_node in the list // in sorted fashion. Note that this function // expects a pointer to head node as this can// modify the head of the input linked liststatic Node sortedInsert(Node head_ref, Node new_node){ Node current = head_ref; // If the list is empty if (current == null) { new_node.next = new_node; head_ref = new_node; } // If the node to be inserted is the smallest // then it has to be the new head else if (current.data >= new_node.data) { // Find the last node of the list as it // will be pointing to the head while (current.next != head_ref) current = current.next; current.next = new_node; new_node.next = head_ref; head_ref = new_node; } else { // Locate the node before the point of insertion while (current.next != head_ref && current.next.data < new_node.data) { current = current.next; } new_node.next = current.next; current.next = new_node; } // Return the new head return head_ref;}// Function to print the nodes of the linked liststatic void printList(Node start){ Node temp; if (start != null) { temp = start; do { System.out.print(temp.data + " "); temp = temp.next; } while (temp != start); }}// Driver codepublic static void main(String args[]){ int arr[] = { 12, 56, 2, 11, 1, 90 }; int list_size, i; // Start with an empty linked list Node start = null; Node temp; // Create linked list from the given array for (i = 0; i < 6; i++) { // Move to a random node if it exists if (start != null) for (int j = 0; j < (Math.random() * 10); j++) start = start.next; temp = create(); temp.data = arr[i]; start = sortedInsert(find_head(start), temp); } // Print the contents of the created list printList(find_head(start));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachfrom random import randint # Node structureclass Node: def __init__(self): self.next = None self.data = 0 # Function to create a nodedef create(): new_node = Node() new_node.next = None return new_node# Function to find and return the headdef find_head(random): # If the list is empty if (random == None): return None head = None var = random # Finding the last node of the linked list # the last node must have the highest value # if no such element is present then all # the nodes of the linked list must be same while (not(var.data > var.next.data or var.next == random)): var = var.next # Return the head return var.next# Function to insert a new_node in the list in # sorted fashion. Note that this function expects# a pointer to head node as this can modify the # head of the input linked listdef sortedInsert(head_ref, new_node): current = head_ref # If the list is empty if (current == None): new_node.next = new_node head_ref = new_node # If the node to be inserted is the smallest # then it has to be the new head elif (current.data >= new_node.data): # Find the last node of the list as it # will be pointing to the head while (current.next != head_ref): current = current.next current.next = new_node new_node.next = head_ref head_ref = new_node else: # Locate the node before the point of insertion while (current.next != head_ref and current.next.data < new_node.data): current = current.next new_node.next = current.next current.next = new_node # Return the new head return head_ref# Function to print the nodes of the linked listdef printList(start): temp = 0 if (start != None): temp = start while True: print(temp.data, end = ' ') temp = temp.next if (temp == start): break# Driver codeif __name__=='__main__': arr = [ 12, 56, 2, 11, 1, 90 ] # Start with an empty linked list start = None; temp = 0 # Create linked list from the given array for i in range(6): # Move to a random node if it exists if (start != None): for j in range(randint(0, 10)): start = start.next temp = create() temp.data = arr[i] start = sortedInsert(find_head(start), temp) # Print the contents of the created list printList(find_head(start)) # This code is contributed by rutvik_56 |
C#
// C# implementation of the approach using System;class GFG { // Node structure public class Node { public Node next; public int data; }; // Function to create a node static Node create() { Node new_node = new Node(); new_node.next = null; return new_node; } // Function to find and return the head static Node find_head(Node random) { // If the list is empty if (random == null) return null; Node var = random; // Finding the last node of the linked list // the last node must have the highest value // if no such element is present then all the nodes // of the linked list must be same while (!(var.data > var.next.data || var.next == random)) { var = var.next; } // Return the head return var.next; } // Function to insert a new_node in the list // in sorted fashion. Note that this function // expects a pointer to head node as this can // modify the head of the input linked list static Node sortedInsert(Node head_ref, Node new_node) { Node current = head_ref; // If the list is empty if (current == null) { new_node.next = new_node; head_ref = new_node; } // If the node to be inserted is the smallest // then it has to be the new head else if (current.data >= new_node.data) { // Find the last node of the list as it // will be pointing to the head while (current.next != head_ref) current = current.next; current.next = new_node; new_node.next = head_ref; head_ref = new_node; } else { // Locate the node before the point of insertion while (current.next != head_ref && current.next.data < new_node.data) { current = current.next; } new_node.next = current.next; current.next = new_node; } // Return the new head return head_ref; } // Function to print the nodes of the linked list static void printList(Node start) { Node temp; if (start != null) { temp = start; do { Console.Write(temp.data + " "); temp = temp.next; } while (temp != start); } } // Driver code public static void Main(String []args) { int []arr = { 12, 56, 2, 11, 1, 90 }; int i; // Start with an empty linked list Node start = null; Node temp; // Create linked list from the given array for (i = 0; i < 6; i++) { // Move to a random node if it exists if (start != null) for (int j = 0; j < (new Random().Next() * 10); j++) start = start.next; temp = create(); temp.data = arr[i]; start = sortedInsert(find_head(start), temp); } // Print the contents of the created list printList(find_head(start)); } }// This code is contributed by PrinciRaj1992 |
Javascript
<script> // javascript implementation of the approach // Node structure class Node { constructor(val) { this.data = val; this.next = null; } } // Function to create a node function create() { var new_node = new Node(); new_node.next = null; return new_node; } // Function to find and return the head function find_head(random) { // If the list is empty if (random == null) return null; var head ,vari = random; // Finding the last node of the linked list // the last node must have the highest value // if no such element is present then all the nodes // of the linked list must be same while (!(vari.data > vari.next.data || vari.next == random)) { vari = vari.next; } // Return the head return vari.next; } // Function to insert a new_node in the list // in sorted fashion. Note that this function // expects a pointer to head node as this can // modify the head of the input linked list function sortedInsert(head_ref, new_node) { var current = head_ref; // If the list is empty if (current == null) { new_node.next = new_node; head_ref = new_node; } // If the node to be inserted is the smallest // then it has to be the new head else if (current.data >= new_node.data) { // Find the last node of the list as it // will be pointing to the head while (current.next != head_ref) current = current.next; current.next = new_node; new_node.next = head_ref; head_ref = new_node; } else { // Locate the node before the point of insertion while (current.next != head_ref && current.next.data < new_node.data) { current = current.next; } new_node.next = current.next; current.next = new_node; } // Return the new head return head_ref; } // Function to print the nodes of the linked list function printList(start) { var temp; if (start != null) { temp = start; do { document.write(temp.data + " "); temp = temp.next; } while (temp != start); } } // Driver code var arr = [ 12, 56, 2, 11, 1, 90 ]; var list_size, i; // Start with an empty linked list var start = null; var temp; // Create linked list from the given array for (i = 0; i < 6; i++) { // Move to a random node if it exists if (start != null) for (j = 0; j < (Math.random() * 10); j++) start = start.next; temp = create(); temp.data = arr[i]; start = sortedInsert(find_head(start), temp); } // Print the contents of the created list printList(find_head(start));// This code is contributed by todaysgaurav </script> |
Output:
1 2 11 12 56 90
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
