Dada una lista enlazada de tamaño N que contiene todos los valores del 1 al N. La tarea es ordenar la lista enlazada en orden creciente.
Ejemplos:
Input : List = 3 -> 5 -> 4 -> 6 -> 1 -> 2 Output : 1 -> 2 -> 3 -> 4 -> 5 -> 6 Input : List = 5 -> 4 -> 3 -> 2 -> 1 Output : 1 -> 2 -> 3 -> 4 -> 5
Enfoque ingenuo : El enfoque más simple es ordenar esta lista enlazada con el uso de cualquier tipo de método de clasificación . Toma O(N*logN) tiempo mínimo.
Enfoque eficiente : un enfoque eficiente es observar que la lista enlazada contiene un total de N elementos y los elementos están numerados del 1 al N. Recorra la lista enlazada y reemplace cada elemento con su posición.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to sort linked list containing
// values from 1 to N
#include <iostream>
using namespace std;
// A linked list node
struct Node {
int data;
struct Node* next;
};
// Function to sort linked list
bool sortList(struct Node* head)
{
int startVal = 1;
while (head != NULL) {
head->data = startVal;
startVal++;
head = head->next;
}
}
// Function to add a node at the
// beginning of Linked List
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// This function prints contents of
// linked list starting from
// the given node
void printList(struct Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Driver program to test above function
int main()
{
struct Node* start = NULL;
/* The constructed linked list is:
3->5->4->6->1->2 */
push(&start, 2);
push(&start, 1);
push(&start, 6);
push(&start, 4);
push(&start, 5);
push(&start, 3);
sortList(start);
printList(start);
return 0;
}
Java
// Java program to sort linked list containing
// values from 1 to N
import java.util.*;
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
};
static Node start;
// Function to sort linked list
static void sortList(Node head)
{
int startVal = 1;
while (head != null)
{
head.data = startVal;
startVal++;
head = head.next;
}
}
// Function to add a node at the
// beginning of Linked List
static void push(Node head_ref,
int new_data)
{
/* allocate node */
Node new_node = new Node();
/* put in the data */
new_node.data = new_data;
/* link the old list off the new node */
new_node.next = head_ref;
/* move the head to point to the new node */
head_ref = new_node;
start = head_ref;
}
// This function prints contents of
// linked list starting from
// the given node
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void main(String[] args)
{
start = null;
/* The constructed linked list is:
3->5->4->6->1->2 */
push(start, 2);
push(start, 1);
push(start, 6);
push(start, 4);
push(start, 5);
push(start, 3);
sortList(start);
printList(start);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to sort linked list # containing values from 1 to N import math # A linked list node class Node: def __init__(self, data): self.data = data self.next = None # Function to sort linked list def sortList(head): startVal = 1 while (head != None): head.data = startVal startVal = startVal + 1 head = head.next # Function to add a node at the # beginning of Linked List def push(head_ref, new_data): # allocate node new_node = Node(new_data) # put in the data new_node.data = new_data # link the old list off the new node new_node.next = head_ref # move the head to point to the new node head_ref = new_node return head_ref # This function prints contents of # linked list starting from # the given node def printList(node): while (node != None): print(node.data, end = " ") node = node.next # Driver Code if __name__=='__main__': head = None # The constructed linked list is: #3.5.4.6.1.2 head = push(head, 2) head = push(head, 1) head = push(head, 6) head = push(head, 4) head = push(head, 5) head = push(head, 3) sortList(head) printList(head) # This code is contributed by Srathore
C#
// C# program to sort linked list
// containing values from 1 to N
using System;
class GFG
{
/* Link list node */
public class Node
{
public int data;
public Node next;
};
static Node start;
// Function to sort linked list
static void sortList(Node head)
{
int startVal = 1;
while (head != null)
{
head.data = startVal;
startVal++;
head = head.next;
}
}
// Function to add a node at the
// beginning of Linked List
static void push(Node head_ref,
int new_data)
{
/* allocate node */
Node new_node = new Node();
/* put in the data */
new_node.data = new_data;
/* link the old list
off the new node */
new_node.next = head_ref;
/* move the head to point
to the new node */
head_ref = new_node;
start = head_ref;
}
// This function prints contents of
// linked list starting from
// the given node
static void printList(Node node)
{
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void Main(String[] args)
{
start = null;
/* The constructed linked list is:
3->5->4->6->1->2 */
push(start, 2);
push(start, 1);
push(start, 6);
push(start, 4);
push(start, 5);
push(start, 3);
sortList(start);
printList(start);
}
}
// This code is contributed
// by Princi Singh
Javascript
<script>
// JavaScript program to sort linked list
// containing values from 1 to N
/* Link list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
var start = null;
// Function to sort linked list
function sortList(head) {
var startVal = 1;
while (head != null) {
head.data = startVal;
startVal++;
head = head.next;
}
}
// Function to add a node at the
// beginning of Linked List
function push(head_ref, new_data) {
/* allocate node */
var new_node = new Node();
/* put in the data */
new_node.data = new_data;
/* link the old list
off the new node */
new_node.next = head_ref;
/* move the head to point
to the new node */
head_ref = new_node;
start = head_ref;
}
// This function prints contents of
// linked list starting from
// the given node
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Driver Code
start = null;
/* The constructed linked list is:
3->5->4->6->1->2 */
push(start, 2);
push(start, 1);
push(start, 6);
push(start, 4);
push(start, 5);
push(start, 3);
sortList(start);
printList(start);
</script>
Producción:
1 2 3 4 5 6
Complejidad temporal: O(n)
Espacio auxiliar: O(1)