Dado el encabezado de una lista enlazada de tamaño N , que consiste en números enteros binarios 0 y 1, la tarea es ordenar la lista enlazada dada .
Ejemplos:
Entrada: head = 1 -> 0 -> 1 -> 0 -> 1 -> 0 -> NULL Salida: 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> NULL
Entrada: cabeza = 1 -> 1 -> 0 -> NULL Salida: 0 -> 1 -> 1 -> NULL
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es realizar la ordenación por fusión o la ordenación por inserción en la lista vinculada dada y ordenarla. La implementación de la clasificación de la lista vinculada mediante la ordenación por fusión y la clasificación de la lista vinculada mediante la ordenación por inserción ya se ha analizado.
Complejidad temporal: O(N * log N)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar contando el número de 1 y 0 en la lista vinculada dada y actualizando el valor de los Nodes en consecuencia en la lista vinculada. Siga los pasos para resolver el problema:
- Recorra la lista enlazada dada y almacene el conteo de 0s y 1s en variables, digamos ceros y unos respectivamente.
- Ahora, recorra la lista enlazada nuevamente y cambie los primeros Nodes de ceros con el valor 0 y luego los Nodes restantes con el valor 1 .
- Después de completar los pasos anteriores, imprima la lista vinculada como la lista ordenada resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node {
public:
int data;
Node* next;
};
// Function to print linked list
void printList(Node* node)
{
// Iterate until node is NOT NULL
while (node != NULL) {
// Print the data
cout << node->data << " ";
node = node->next;
}
}
// Function to sort the linked list
// consisting of 0s and 1s
void sortList(Node* head)
{
// Base Case
if ((head == NULL)
|| (head->next == NULL)) {
return;
}
// Store the count of 0s and 1s
int count0 = 0, count1 = 0;
// Stores the head node
Node* temp = head;
// Traverse the list Head
while (temp != NULL) {
// If node->data value is 0
if (temp->data == 0) {
// Increment count0 by 1
count0++;
}
// Otherwise, increment the
// count of 1s
else {
count1++;
}
// Update the temp node
temp = temp->next;
}
// Update the temp to head
temp = head;
// Traverse the list and update
// the first count0 nodes as 0
while (count0--) {
temp->data = 0;
temp = temp->next;
}
// Now, update the value of the
// remaining count1 nodes as 1
while (count1--) {
temp->data = 1;
temp = temp->next;
}
// Print the Linked List
printList(head);
}
// Function to push a node
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 of the
// new node
new_node->next = (*head_ref);
// Move the head to point to
// the new node
(*head_ref) = new_node;
}
// Driver Code
int main(void)
{
Node* head = NULL;
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 1);
push(&head, 1);
push(&head, 1);
push(&head, 1);
push(&head, 0);
sortList(head);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Link list node
static class Node {
int data;
Node next;
};
// Function to print linked list
static void printList(Node node)
{
// Iterate until node is NOT null
while (node != null) {
// Print the data
System.out.print(node.data+ " ");
node = node.next;
}
}
// Function to sort the linked list
// consisting of 0s and 1s
static void sortList(Node head)
{
// Base Case
if ((head == null)
|| (head.next == null)) {
return;
}
// Store the count of 0s and 1s
int count0 = 0, count1 = 0;
// Stores the head node
Node temp = head;
// Traverse the list Head
while (temp != null) {
// If node.data value is 0
if (temp.data == 0) {
// Increment count0 by 1
count0++;
}
// Otherwise, increment the
// count of 1s
else {
count1++;
}
// Update the temp node
temp = temp.next;
}
// Update the temp to head
temp = head;
// Traverse the list and update
// the first count0 nodes as 0
while (count0>0) {
temp.data = 0;
temp = temp.next;
count0--;
}
// Now, update the value of the
// remaining count1 nodes as 1
while (count1>0) {
temp.data = 1;
temp = temp.next;
count1--;
}
// Print the Linked List
printList(head);
}
// Function to push a node
static Node 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 of the
// new node
new_node.next = head_ref;
// Move the head to point to
// the new node
head_ref = new_node;
return head_ref;
}
// Driver Code
public static void main(String[] args)
{
Node head = null;
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 0);
sortList(head);
}
}
// This code is contributed by umadevi9616
Python3
# Python program for the above approach # Link list Node class Node: def __init__(self): self.data = 0; self.next = None; # Function to print linked list def printList(Node): # Iterate until Node is NOT None while (Node != None): # Print data print(Node.data, end=" "); Node = Node.next; # Function to sort the linked list # consisting of 0s and 1s def sortList(head): # Base Case if ((head == None) or (head.next == None)): return; # Store the count of 0s and 1s count0 = 0; count1 = 0; # Stores the head Node temp = head; # Traverse the list Head while (temp != None): # If Node.data value is 0 if (temp.data == 0): # Increment count0 by 1 count0 += 1; # Otherwise, increment the # count of 1s else: count1 += 1; # Update the temp Node temp = temp.next; # Update the temp to head temp = head; # Traverse the list and update # the first count0 Nodes as 0 while (count0 > 0): temp.data = 0; temp = temp.next; count0 -= 1; # Now, update the value of the # remaining count1 Nodes as 1 while (count1 > 0): temp.data = 1; temp = temp.next; count1 -= 1; # Print the Linked List printList(head); # Function to push a Node def push(head_ref, new_data): # Allocate Node new_Node = Node(); # Put in the data new_Node.data = new_data; # Link the old list of the # new Node new_Node.next = head_ref; # Move the head to point to # the new Node head_ref = new_Node; return head_ref; # Driver Code if __name__ == '__main__': head = None; head = push(head, 0); head = push(head, 1); head = push(head, 0); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 0); sortList(head); # This code is contributed by umadevi9616
C#
// C# program for the above approach
using System;
public class GFG {
// Link list node
public class Node {
public int data;
public Node next;
};
// Function to print linked list
static void printList(Node node) {
// Iterate until node is NOT null
while (node != null) {
// Print the data
Console.Write(node.data + " ");
node = node.next;
}
}
// Function to sort the linked list
// consisting of 0s and 1s
static void sortList(Node head) {
// Base Case
if ((head == null) || (head.next == null)) {
return;
}
// Store the count of 0s and 1s
int count0 = 0, count1 = 0;
// Stores the head node
Node temp = head;
// Traverse the list Head
while (temp != null) {
// If node.data value is 0
if (temp.data == 0) {
// Increment count0 by 1
count0++;
}
// Otherwise, increment the
// count of 1s
else {
count1++;
}
// Update the temp node
temp = temp.next;
}
// Update the temp to head
temp = head;
// Traverse the list and update
// the first count0 nodes as 0
while (count0 > 0) {
temp.data = 0;
temp = temp.next;
count0--;
}
// Now, update the value of the
// remaining count1 nodes as 1
while (count1 > 0) {
temp.data = 1;
temp = temp.next;
count1--;
}
// Print the Linked List
printList(head);
}
// Function to push a node
static Node 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 of the
// new node
new_node.next = head_ref;
// Move the head to point to
// the new node
head_ref = new_node;
return head_ref;
}
// Driver Code
public static void Main(String[] args) {
Node head = null;
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 0);
sortList(head);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program for the above approach
// Link list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to print linked list
function printList(node) {
// Iterate until node is NOT null
while (node != null) {
// Print the data
document.write(node.data + " ");
node = node.next;
}
}
// Function to sort the linked list
// consisting of 0s and 1s
function sortList(head)
{
// Base Case
if ((head == null) || (head.next == null)) {
return;
}
// Store the count of 0s and 1s
var count0 = 0, count1 = 0;
// Stores the head node
var temp = head;
// Traverse the list Head
while (temp != null) {
// If node.data value is 0
if (temp.data == 0) {
// Increment count0 by 1
count0++;
}
// Otherwise, increment the
// count of 1s
else {
count1++;
}
// Update the temp node
temp = temp.next;
}
// Update the temp to head
temp = head;
// Traverse the list and update
// the first count0 nodes as 0
while (count0 > 0) {
temp.data = 0;
temp = temp.next;
count0--;
}
// Now, update the value of the
// remaining count1 nodes as 1
while (count1 > 0) {
temp.data = 1;
temp = temp.next;
count1--;
}
// Print the Linked List
printList(head);
}
// Function to push a node
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 of the
// new node
new_node.next = head_ref;
// Move the head to point to
// the new node
head_ref = new_node;
return head_ref;
}
// Driver Code
var head = null;
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 0);
sortList(head);
// This code is contributed by umadevi9616
</script>
Producción:
0 0 0 1 1 1 1 1 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nirajgusain5 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA