Inserción en una lista enlazada circular ordenada cuando se proporciona un puntero aleatorio

Dada una array arr[] de enteros y un puntero a un Node aleatorio de una lista enlazada ordenada circular (inicialmente vacía), la tarea es insertar todos los elementos de arr[] en la lista enlazada circular.

Ejemplos:  

Entrada: arr[] = {12, 56, 2, 11, 1, 90} 
Salida: 1 2 11 12 56 90

Entrada: arr[] = {6, 2, 78, 45, 200} 
Salida: 2 6 45 78 200 

Enfoque: se nos da un puntero aleatorio a un Node en la lista enlazada circular y tenemos que encontrar el encabezado de la lista enlazada circular para insertar el Node en una lista enlazada ordenada. 
La inserción en una lista enlazada ordenada cuando se da el encabezado se explica en este artículo. 
Para encontrar el encabezado de la lista enlazada ordenada circular: 

• Encuentre el último Node de la lista enlazada (el último Node será mayor que su sucesor, es decir, el primer elemento).
• Una vez que se encuentra el encabezado de la lista vinculada, los elementos se pueden insertar utilizando el mismo enfoque que se describe en el artículo anterior.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Node structure
struct Node {
    Node* next;
    int data;
};
 
// Function to create a node
Node* create()
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->next = NULL;
 
    return new_node;
}
 
// Function to find and return the head
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 list
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
void printList(Node* start)
{
    Node* temp;
 
    if (start != NULL) {
        temp = start;
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != start);
    }
}
 
// Driver code
int 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 implementation of the approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
     
// Node structure
static class Node
{
    Node next;
    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 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 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
        {
            System.out.print(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 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 implementation of the approach
from random import randint
 
# Node structure
class Node:
 
    def __init__(self):
 
        self.next = None
        self.data = 0
   
# Function to create a node
def create():
 
    new_node = Node()
    new_node.next = None
    return new_node
 
# Function to find and return the head
def 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 list
def 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 list
def printList(start):
 
    temp = 0
 
    if (start != None):
        temp = start
 
        while True:
            print(temp.data, end = ' ')
            temp = temp.next
             
            if (temp == start):
                break
 
# Driver code
if __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# 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

<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>

1 2 11 12 56 90

Complejidad temporal: O(N)
Espacio auxiliar: O(N)