Ordene una lista enlazada de 0, 1 y 2 cambiando los enlaces

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *