Dada una lista ordenada ordenada y un valor para insertar, escriba una función para insertar el valor de forma ordenada.
Lista enlazada inicial
Lista enlazada después de la inserción de 9
Algoritmo:
permite que la lista de enlaces de entrada se ordene en orden creciente.
1) If Linked list is empty then make the node as head and return it. 2) If the value of the node to be inserted is smaller than the value of the head node, then insert the node at the start and make it head. 3) In a loop, find the appropriate node after which the input node (let 9) is to be inserted. To find the appropriate node start from the head, keep moving until you reach a node GN (10 in the below diagram) who's value is greater than the input node. The node just before GN is the appropriate node (7). 4) Insert the node (9) after the appropriate node (7) found in step 3.
Implementación:
C++
/* Program to insert in a sorted list */
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
/* function to insert a new_node
in a list. Note that this
function expects a pointer to
head_ref as this can modify the
head of the input linked list
(similar to push())*/
void sortedInsert(Node** head_ref,
Node* new_node)
{
Node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
/* Locate the node before the
point of insertion */
current = *head_ref;
while (current->next != NULL
&& current->next->data
< new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* BELOW FUNCTIONS ARE JUST
UTILITY TO TEST sortedInsert */
/* A utility function to
create a new node */
Node* newNode(int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void printList(Node* head)
{
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
cout << "Created Linked List\n";
printList(head);
return 0;
}
// This is code is contributed by rathbhupendra
C
/* Program to insert in a sorted list */
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* function to insert a new_node
in a list. Note that this
function expects a pointer
to head_ref as this can modify the
head of the input linked
list (similar to push())*/
void sortedInsert(struct Node** head_ref,
struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
/* Locate the node before
the point of insertion */
current = *head_ref;
while (current->next != NULL
&& current->next->data < new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */
/* A utility function to create a new node */
struct Node* newNode(int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(
sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf("\n Created Linked List\n");
printList(head);
return 0;
}
Java
// Java Program to insert in a sorted list
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* function to insert a
new_node in a list. */
void sortedInsert(Node new_node)
{
Node current;
/* Special case for head node */
if (head == null || head.data
>= new_node.data) {
new_node.next = head;
head = new_node;
}
else {
/* Locate the node before point of insertion. */
current = head;
while (current.next != null
&& current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
/*Utility functions*/
/* Function to create a node */
Node newNode(int data)
{
Node x = new Node(data);
return x;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
/* Driver function to test above methods */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
Node new_node;
new_node = llist.newNode(5);
llist.sortedInsert(new_node);
new_node = llist.newNode(10);
llist.sortedInsert(new_node);
new_node = llist.newNode(7);
llist.sortedInsert(new_node);
new_node = llist.newNode(3);
llist.sortedInsert(new_node);
new_node = llist.newNode(1);
llist.sortedInsert(new_node);
new_node = llist.newNode(9);
llist.sortedInsert(new_node);
System.out.println("Created Linked List");
llist.printList();
}
}
/* This code is contributed by Rajat Mishra */
Python
# Python program to insert in a sorted list # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None def sortedInsert(self, new_node): # Special case for the empty linked list if self.head is None: new_node.next = self.head self.head = new_node # Special case for head at end elif self.head.data >= new_node.data: new_node.next = self.head self.head = new_node else : # Locate the node before the point of insertion current = self.head while(current.next is not None and current.next.data < new_node.data): current = current.next new_node.next = current.next current.next = new_node # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print it the LinkedList def printList(self): temp = self.head while(temp): print temp.data, temp = temp.next # Driver program llist = LinkedList() new_node = Node(5) llist.sortedInsert(new_node) new_node = Node(10) llist.sortedInsert(new_node) new_node = Node(7) llist.sortedInsert(new_node) new_node = Node(3) llist.sortedInsert(new_node) new_node = Node(1) llist.sortedInsert(new_node) new_node = Node(9) llist.sortedInsert(new_node) print "Create Linked List" llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# Program to insert in a sorted list
using System;
public class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
/* function to insert a new_node in a list. */
void sortedInsert(Node new_node)
{
Node current;
/* Special case for head node */
if (head == null || head.data >= new_node.data) {
new_node.next = head;
head = new_node;
}
else {
/* Locate the node before
point of insertion. */
current = head;
while (current.next != null && current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
/*Utility functions*/
/* Function to create a node */
Node newNode(int data)
{
Node x = new Node(data);
return x;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
}
/* Driver code */
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
Node new_node;
new_node = llist.newNode(5);
llist.sortedInsert(new_node);
new_node = llist.newNode(10);
llist.sortedInsert(new_node);
new_node = llist.newNode(7);
llist.sortedInsert(new_node);
new_node = llist.newNode(3);
llist.sortedInsert(new_node);
new_node = llist.newNode(1);
llist.sortedInsert(new_node);
new_node = llist.newNode(9);
llist.sortedInsert(new_node);
Console.WriteLine("Created Linked List");
llist.printList();
}
}
/* This code is contributed by 29AjayKumar */
Javascript
<script>
// javascript Program to insert in a sorted list
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/*
* function to insert a new_node in a list.
*/
function sortedInsert( new_node) {
var current;
/* Special case for head node */
if (head == null || head.data >= new_node.data) {
new_node.next = head;
head = new_node;
} else {
/* Locate the node before point of insertion. */
current = head;
while (current.next != null && current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
/* Utility functions */
/* Function to create a node */
function newNode(data) {
x = new Node(data);
return x;
}
/* Function to print linked list */
function printList() {
temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
/* Driver function to test above methods */
var new_node;
new_node = newNode(5);
sortedInsert(new_node);
new_node = newNode(10);
sortedInsert(new_node);
new_node = newNode(7);
sortedInsert(new_node);
new_node = newNode(3);
sortedInsert(new_node);
new_node = newNode(1);
sortedInsert(new_node);
new_node = newNode(9);
sortedInsert(new_node);
document.write("Created Linked List<br/>");
printList();
// This code is contributed by aashish1995
</script>
Producción:
Created Linked List 1 3 5 7 9 10
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido de la lista. - Espacio Auxiliar: O(1).
No se necesita espacio adicional.
Implementación más corta usando punteros dobles:
gracias a Murat M Ozturk por proporcionar esta solución. Consulte el comentario de Murat M Ozturk a continuación para ver la función completa. El código usa doble puntero para realizar un seguimiento del siguiente puntero del Node anterior (después del cual se inserta un nuevo Node).
Tenga en cuenta que la línea de abajo en el código cambia actual para tener la dirección del siguiente puntero en un Node.
current = &((*current)->next);
Además, tenga en cuenta los comentarios a continuación.
/* Copies the value-at-address current to
new_node's next pointer*/
new_node->next = *current;
/* Fix next pointer of the node (using its address)
after which new_node is being inserted */
*current = new_node;
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA