Dada una lista enlazada de 0, 1 y 2, ordénela.
Ejemplos:
C++
// CPP Program to sort a linked list 0s, 1s
// or 2s by changing links
#include <bits/stdc++.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
Node* newNode(int data);
// Sort a linked list of 0s, 1s and 2s
// by changing pointers.
Node* sortList(Node* head)
{
if (!head || !(head->next))
return head;
// Create three dummy nodes to point to beginning of
// three linked lists. These dummy nodes are created to
// avoid many null checks.
Node* zeroD = newNode(0);
Node* oneD = newNode(0);
Node* twoD = newNode(0);
// Initialize current pointers for three
// lists and whole list.
Node *zero = zeroD, *one = oneD, *two = twoD;
// Traverse list
Node* curr = head;
while (curr) {
if (curr->data == 0) {
zero->next = curr;
zero = zero->next;
}
else if (curr->data == 1) {
one->next = curr;
one = one->next;
}
else {
two->next = curr;
two = two->next;
}
curr = curr->next;
}
// Attach three lists
zero->next = (oneD->next) ? (oneD->next) : (twoD->next);
one->next = twoD->next;
two->next = NULL;
// Updated head
head = zeroD->next;
// Delete dummy nodes
delete zeroD;
delete oneD;
delete twoD;
return head;
}
// Function to create and return a node
Node* newNode(int data)
{
// allocating space
Node* newNode = new Node;
// inserting the required data
newNode->data = data;
newNode->next = NULL;
}
/* Function to print linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
/* Driver program to test above function*/
int main(void)
{
// Creating the list 1->2->4->5
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(0);
head->next->next->next = newNode(1);
printf("Linked List Before Sorting\n");
printList(head);
head = sortList(head);
printf("Linked List After Sorting\n");
printList(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C Program to sort a linked list 0s, 1s
// or 2s by changing links
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* newNode(int data);
// Sort a linked list of 0s, 1s and 2s
// by changing pointers.
Node* sortList(Node* head)
{
if (!head || !(head->next))
return head;
// Create three dummy nodes to point to beginning of
// three linked lists. These dummy nodes are created to
// avoid many null checks.
Node* zeroD = newNode(0);
Node* oneD = newNode(0);
Node* twoD = newNode(0);
// Initialize current pointers for three
// lists and whole list.
Node *zero = zeroD, *one = oneD, *two = twoD;
// Traverse list
Node* curr = head;
while (curr) {
if (curr->data == 0) {
zero->next = curr;
zero = zero->next;
}
else if (curr->data == 1) {
one->next = curr;
one = one->next;
}
else {
two->next = curr;
two = two->next;
}
curr = curr->next;
}
// Attach three lists
zero->next = (oneD->next) ? (oneD->next) : (twoD->next);
one->next = twoD->next;
two->next = NULL;
// Updated head
head = zeroD->next;
// Delete dummy nodes
free(zeroD);
free(oneD);
free(twoD);
return head;
}
// Function to create and return a node
Node* newNode(int data)
{
// allocating space
Node* newNode = (Node*)malloc(sizeof(Node));
// inserting the required data
newNode->data = data;
newNode->next = NULL;
}
/* Function to print linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
/* Driver program to test above function*/
int main(void)
{
// Creating the list 1->2->4->5
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(0);
head->next->next->next = newNode(1);
printf("Linked List Before Sorting\n");
printList(head);
head = sortList(head);
printf("Linked List After Sorting\n");
printList(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java Program to sort a linked list 0s, 1s
// or 2s by changing links
public class Sort012 {
// Sort a linked list of 0s, 1s and 2s
// by changing pointers.
public static Node sortList(Node head)
{
if(head==null || head.next==null)
{
return head;
}
// Create three dummy nodes to point to
// beginning of three linked lists. These
// dummy nodes are created to avoid many
// null checks.
Node zeroD = new Node(0);
Node oneD = new Node(0);
Node twoD = new Node(0);
// Initialize current pointers for three
// lists and whole list.
Node zero = zeroD, one = oneD, two = twoD;
// Traverse list
Node curr = head;
while (curr!=null)
{
if (curr.data == 0)
{
zero.next = curr;
zero = zero.next;
curr = curr.next;
}
else if (curr.data == 1)
{
one.next = curr;
one = one.next;
curr = curr.next;
}
else
{
two.next = curr;
two = two.next;
curr = curr.next;
}
}
// Attach three lists
zero.next = (oneD.next!=null)
? (oneD.next) : (twoD.next);
one.next = twoD.next;
two.next = null;
// Updated head
head = zeroD.next;
return head;
}
// function to create and return a node
public static Node newNode(int data)
{
// allocating space
Node newNode = new Node(data);
newNode.next = null;
return newNode;
}
/* Function to print linked list */
public static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data+" ");
node = node.next;
}
}
public static void main(String args[]) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(0);
head.next.next.next = new Node(1);
System.out.println("
Linked List Before Sorting");
printList(head);
head = sortList(head);
System.out.println("
\nLinked List After Sorting");
printList(head);
}
}
class Node
{
int data;
Node next;
Node(int data)
{
this.data=data;
}
}
//This code is contributed by Gaurav Tiwari
Python3
# Python3 Program to sort a linked list
# 0s, 1s or 2s by changing links
import math
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
#Node* newNode( data)
# Sort a linked list of 0s, 1s and 2s
# by changing pointers.
def sortList(head):
if (head == None or
head.next == None):
return head
# Create three dummy nodes to point to
# beginning of three linked lists.
# These dummy nodes are created to
# avoid many None checks.
zeroD = Node(0)
oneD = Node(0)
twoD = Node(0)
# Initialize current pointers for three
# lists and whole list.
zero = zeroD
one = oneD
two = twoD
# Traverse list
curr = head
while (curr):
if (curr.data == 0):
zero.next = curr
zero = zero.next
curr = curr.next
elif(curr.data == 1):
one.next = curr
one = one.next
curr = curr.next
else:
two.next = curr
two = two.next
curr = curr.next
# Attach three lists
zero.next = (oneD.next) if (oneD.next ) \
else (twoD.next)
one.next = twoD.next
two.next = None
# Updated head
head = zeroD.next
# Delete dummy nodes
return head
# function to create and return a node
def newNode(data):
# allocating space
newNode = Node(data)
# inserting the required data
newNode.data = data
newNode.next = None
return newNode
# Function to print linked list
def printList(node):
while (node != None):
print(node.data, end = " ")
node = node.next
# Driver Code
if __name__=='__main__':
# Creating the list 1.2.4.5
head = newNode(1)
head.next = newNode(2)
head.next.next = newNode(0)
head.next.next.next = newNode(1)
print("Linked List Before Sorting")
printList(head)
head = sortList(head)
print("\nLinked List After Sorting")
printList(head)
# This code is contributed by Srathore
C#
// C# Program to sort a linked list 0s, 1s
// or 2s by changing links
using System;
public class Sort012
{
// Sort a linked list of 0s, 1s and 2s
// by changing pointers.
public static Node sortList(Node head)
{
if(head == null || head.next == null)
{
return head;
}
// Create three dummy nodes to point to
// beginning of three linked lists. These
// dummy nodes are created to avoid many
// null checks.
Node zeroD = new Node(0);
Node oneD = new Node(0);
Node twoD = new Node(0);
// Initialize current pointers for three
// lists and whole list.
Node zero = zeroD, one = oneD, two = twoD;
// Traverse list
Node curr = head;
while (curr != null)
{
if (curr.data == 0)
{
zero.next = curr;
zero = zero.next;
curr = curr.next;
}
else if (curr.data == 1)
{
one.next = curr;
one = one.next;
curr = curr.next;
}
else
{
two.next = curr;
two = two.next;
curr = curr.next;
}
}
// Attach three lists
zero.next = (oneD.next != null)
? (oneD.next) : (twoD.next);
one.next = twoD.next;
two.next = null;
// Updated head
head = zeroD.next;
return head;
}
// function to create and return a node
public static Node newNode(int data)
{
// allocating space
Node newNode = new Node(data);
newNode.next = null;
return newNode;
}
/* Function to print linked list */
public static void printList(Node node)
{
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver code
public static void Main()
{
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(0);
head.next.next.next = new Node(1);
Console.WriteLine("Linked List Before Sorting");
printList(head);
head = sortList(head);
Console.WriteLine("\nLinked List After Sorting");
printList(head);
}
}
public class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript Program to sort a
// linked list 0s, 1s
// or 2s by changing links
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Sort a linked list of 0s, 1s and 2s
// by changing pointers.
function sortList(head) {
if (head == null || head.next == null) {
return head;
}
// Create three dummy nodes to point to
// beginning of three linked lists. These
// dummy nodes are created to afunction many
// null checks.
var zeroD = new Node(0);
var oneD = new Node(0);
var twoD = new Node(0);
// Initialize current pointers for three
// lists and whole list.
var zero = zeroD, one = oneD, two = twoD;
// Traverse list
var curr = head;
while (curr != null) {
if (curr.data == 0) {
zero.next = curr;
zero = zero.next;
curr = curr.next;
} else if (curr.data == 1) {
one.next = curr;
one = one.next;
curr = curr.next;
} else {
two.next = curr;
two = two.next;
curr = curr.next;
}
}
// Attach three lists
zero.next = (oneD.next != null) ?
(oneD.next) : (twoD.next);
one.next = twoD.next;
two.next = null;
// Updated head
head = zeroD.next;
return head;
}
// function to create and return a node
function newNode(data) {
// allocating space
var newNode = new Node(data);
newNode.next = null;
return newNode;
}
/* Function to print linked list */
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
var head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(0);
head.next.next.next = new Node(1);
document.write(
"Linked List Before Sorting<br/>"
);
printList(head);
head = sortList(head);
document.write(
"<br/>Linked List After Sorting<br/>"
);
printList(head);
// This code contributed by gauravrajput1
</script>
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