Рубрики

Сортировать связанный список 0, 1 и 2

Связанный список, Сортировка

Учитывая связанный список 0, 1 и 2, сортируйте его.

Примеры :

Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL

Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL

Источник: Microsoft Интервью | Комплект 1

Следующие шаги могут быть использованы для сортировки данного связанного списка.

  • Пройдите по списку и посчитайте количество 0, 1 и 2. Пусть счетами будут n1, n2 и n3 соответственно.
  • Снова пройдите по списку, заполните первые n1 узлы 0, затем n2 узлы 1 и, наконец, n3 узлы 2.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ Программа для сортировки связанного списка 0, 1 или 2
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

class Node 

{ 

    public:

    int data; 

    Node* next; 

}; 

  
// Функция для сортировки связанного списка 0, 1 и 2

void sortList(Node *head) 

{ 

    int count[3] = {0, 0, 0}; // Инициализировать счетчик '0', '1' и '2' как 0

    Node *ptr = head; 

  

    / * подсчитать общее количество '0', '1' и '2'

    * count [0] будет хранить общее количество '0'

    * count [1] будет хранить общее количество единиц

    * count [2] будет хранить общее количество '2's * /

    while (ptr != NULL) 

    { 

        count[ptr->data] += 1; 

        ptr = ptr->next; 

    } 

  

    int i = 0; 

    ptr = head; 

  

    / * Допустим, скажем, count [0] = n1, count [1] = n2 и count [2] = n3

    * теперь начинайте обход списка с головного узла,

    * 1) заполнить список 0, пока n1> 0

    * 2) заполнить список 1 до n2> 0

    * 3) заполнить список 2, до n3> 0 * /

    while (ptr != NULL) 

    { 

        if (count[i] == 0) 

            ++i; 

        else

        { 

            ptr->data = i; 

            --count[i]; 

            ptr = ptr->next; 

        } 

    } 

} 

  
/ * Функция подтолкнуть узел * /

void push (Node** head_ref, int new_data) 

{ 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node; 

} 

  
/ * Функция для печати связанного списка * /

void printList(Node *node) 

{ 

    while (node != NULL) 

    { 

        cout << node->data << " "; 

        node = node->next; 

    } 

    cout << endl; 

} 

  
/ * Код водителя * /

int main(void) 

{ 

    Node *head = NULL; 

    push(&head, 0); 

    push(&head, 1); 

    push(&head, 0); 

    push(&head, 2); 

    push(&head, 1); 

    push(&head, 1); 

    push(&head, 2); 

    push(&head, 1); 

    push(&head, 2); 

  

    cout << "Linked List Before Sorting\n"; 

    printList(head); 

  

    sortList(head); 

  

    cout << "Linked List After Sorting\n"; 

    printList(head); 

  

    return 0; 

} 

  
// Этот код предоставлен rathbhupendra

С

// C Программа для сортировки связанного списка 0, 1 или 2
#include<stdio.h>
#include<stdlib.h>

  
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  
// Функция для сортировки связанного списка 0, 1 и 2

void sortList(struct Node *head)

{

    int count[3] = {0, 0, 0};  // Инициализировать счетчик '0', '1' и '2' как 0

    struct Node *ptr = head;

  

    / * подсчитать общее количество '0', '1' и '2'

     * count [0] будет хранить общее количество '0'

     * count [1] будет хранить общее количество единиц

     * count [2] будет хранить общее количество '2's * /

    while (ptr != NULL)

    {

        count[ptr->data] += 1;

        ptr = ptr->next;

    }

  

    int i = 0;

    ptr = head;

  

    / * Допустим, скажем, count [0] = n1, count [1] = n2 и count [2] = n3

     * теперь начинайте обход списка с головного узла,

     * 1) заполнить список 0, пока n1> 0

     * 2) заполнить список 1 до n2> 0

     * 3) заполнить список 2, до n3> 0 * /

    while (ptr != NULL)

    {

        if (count[i] == 0)

            ++i;

        else

        {

            ptr->data = i;

            --count[i];

            ptr = ptr->next;

        }

    }

}

  
/ * Функция подтолкнуть узел * /

void push (struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node =

        (struct Node*) malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data  = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref)    = new_node;

}

  
/ * Функция для печати связанного списка * /

void printList(struct Node *node)

{

    while (node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

    }

    printf("n");

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main(void)

{

    struct Node *head = NULL;

    push(&head, 0);

    push(&head, 1);

    push(&head, 0);

    push(&head, 2);

    push(&head, 1);

    push(&head, 1);

    push(&head, 2);

    push(&head, 1);

    push(&head, 2);

  

    printf("Linked List Before Sorting\n");

    printList(head);

  

    sortList(head);

  

    printf("Linked List After Sorting\n");

    printList(head);

  

    return 0;

}

Джава

// Java-программа для сортировки связанного списка 0, 1 и 2

class LinkedList

{

    Node head;  // заголовок списка

   

    / * Узел связанного списка * /

    class Node

    {

        int data;

        Node next;

        Node(int d) {data = d; next = null; }

    }

  

    void sortList()

    {

       // инициализировать счетчик 0 1 и 2 как 0

       int count[] = {0, 0, 0}; 

         

       Node ptr = head;

         

       / * подсчитать общее количество '0', '1' и '2'

        * count [0] будет хранить общее количество '0'

        * count [1] будет хранить общее количество единиц

        * count [2] будет хранить общее количество '2's * /

       while (ptr != null) 

       {

            count[ptr.data]++;

            ptr = ptr.next;

       }

  

       int i = 0;

       ptr = head;

  

       / * Допустим, скажем, count [0] = n1, count [1] = n2 и count [2] = n3

        * теперь начинайте обход списка с головного узла,

        * 1) заполнить список 0, пока n1> 0

        * 2) заполнить список 1 до n2> 0

        * 3) заполнить список 2, до n3> 0 * /

        while (ptr != null) 

        {

            if (count[i] == 0)

                i++;

            else 

            {

               ptr.data= i;

               --count[i];

               ptr = ptr.next;

            }

         }

    }                       

  

                     

    / * Сервисные функции * /

  

    / * Вставляет новый узел в начало списка. * /

    public void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

   

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

   

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    / * Функция для печати связанного списка * /

    void printList()

    {

        Node temp = head;

        while (temp != null)

        {

           System.out.print(temp.data+" ");

           temp = temp.next;

        }  

        System.out.println();

    }

  

     / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String args[])

    {

        LinkedList llist = new LinkedList();

          

        / * Построенный связанный список: 1-> 2-> 3-> 4-> 5-> 6-> 7->

           8-> 8-> 9-> ноль * /

        llist.push(0);

        llist.push(1);

        llist.push(0);

        llist.push(2);

        llist.push(1);

        llist.push(1);

        llist.push(2);

        llist.push(1);

        llist.push(2);

          

        System.out.println("Linked List before sorting");

        llist.printList();

          

        llist.sortList();

  

        System.out.println("Linked List after sorting");

        llist.printList();

    }

} 
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python для сортировки связанного списка 0, 1 и 2

class LinkedList(object):

    def __init__(self):

  

         # заголовок списка

         self.head = None

  

    # Узел связанного списка

    class Node(object):

        def __init__(self, d):

            self.data = d

            self.next = None

  

    def sortList(self):

  

        # инициализировать счетчик 0 1 и 2 как 0

        count = [0, 0, 0]

  

        ptr = self.head

  

        # общее количество «0», «1» и «2»

        # * count [0] будет хранить общее количество '0'

        # * count [1] будет хранить общее количество единиц

        # * count [2] будет хранить общее количество '2

        while ptr != None:

            count[ptr.data]+=1

            ptr = ptr.next

  

        i = 0

        ptr = self.head

  

        # Допустим, что count [0] = n1, count [1] = n2 и count [2] = n3

        # * теперь начинаем обход списка с головного узла,

        # * 1) заполнить список 0, пока n1> 0

        # * 2) заполнить список 1, пока n2> 0

        # * 3) заполнить список 2 до n3> 0

        while ptr != None:

            if count[i] == 0:

                i+=1

            else:

                ptr.data = i

                count[i]-=1

                ptr = ptr.next

  

  

    # Сервисные функции

    # Вставляет новый узел в начало списка.

    def push(self, new_data):

  

        # 1 & 2: выделить узел &

        # Вставьте данные

        new_node = self.Node(new_data)

  

        # 3. Сделать следующий из нового узла в качестве головы

        new_node.next = self.head

  

        # 4. Переместите голову, чтобы указать на новый узел

        self.head = new_node

  

    # Функция для печати связанного списка

    def printList(self):

        temp = self.head

        while temp != None:

            print str(temp.data),

            temp = temp.next

        print ''

  
# Драйверная программа для проверки вышеуказанных функций

llist = LinkedList()

llist.push(0)

llist.push(1)

llist.push(0)

llist.push(2)

llist.push(1)

llist.push(1)

llist.push(2)

llist.push(1)

llist.push(2)

  

print "Linked List before sorting"

llist.printList()

  
llist.sortList()

  

print "Linked List after sorting"

llist.printList()

  
# Этот код предоставлен BHAVYA JAIN

C #

// C # программа для сортировки связанных
// список 0, 1 и 2

using System;

  

public class LinkedList

{

    Node head; // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        public int data;

        public Node next;

        public Node(int d) 

        {

            data = d; next = null;

        }

    }

  

    void sortList()

    {

          

        // инициализировать счетчик 0 1 и 2 как 0

        int []count = {0, 0, 0}; 

          

        Node ptr = head;

          

        / * подсчитать общее количество '0', '1' и '2'

        * count [0] будет хранить общее количество '0'

        * count [1] будет хранить общее количество единиц

        * count [2] будет хранить общее количество '2's * /

        while (ptr != null) 

        {

               count[ptr.data]++;

            ptr = ptr.next;

        }

  

        int i = 0;

        ptr = head;

  

        / * Допустим, скажем, count [0] = n1, count [1] = n2 и count [2] = n3

        * теперь начинайте обход списка с головного узла,

        * 1) заполнить список 0, пока n1> 0

        * 2) заполнить список 1 до n2> 0

        * 3) заполнить список 2, до n3> 0 * /

        while (ptr != null) 

        {

            if (count[i] == 0)

                i++;

            else

            {

                ptr.data= i;

                --count[i];

                ptr = ptr.next;

            }

        }

    }                     

  

                      

    / * Сервисные функции * /

  

    / * Вставляет новый узел в начало списка. * /

    public void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    / * Функция для печати связанного списка * /

    void printList()

    {

        Node temp = head;

        while (temp != null)

        {

            Console.Write(temp.data+" ");

            temp = temp.next;

        } 

        Console.WriteLine();

    }

  

    / * Код водителя * /

    public static void Main(String []args)

    {

        LinkedList llist = new LinkedList();

          

        / * Построенный связанный список: 1-> 2-> 3-> 4->

        5-> 6-> 7-> 8-> 8-> 9-> ноль * /

        llist.push(0);

        llist.push(1);

        llist.push(0);

        llist.push(2);

        llist.push(1);

        llist.push(1);

        llist.push(2);

        llist.push(1);

        llist.push(2);

          

        Console.WriteLine("Linked List before sorting");

        llist.printList();

          

        llist.sortList();

  

        Console.WriteLine("Linked List after sorting");

        llist.printList();

    }

} 

  
/ * Этот код предоставлен 29AjayKumar * /


Выход:

Linked List Before Sorting
2  1  2  1  1  2  0  1  0
Linked List After Sorting
0  0  1  1  1  1  2  2  2

Сложность времени: O (n), где n — количество узлов в связанном списке.
Вспомогательное пространство: O (1)


Сортировать связанный список 0, 1 и 2 путем изменения ссылок

Эта статья составлена Нарендрой Кангралкар . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сортировать связанный список 0, 1 и 2

0.00 (0%) 0 votes