Рубрики

Подсчет дубликатов в заданном связанном списке

Дан связанный список. Задача состоит в том, чтобы подсчитать количество повторяющихся узлов в связанном списке.
Примеры:

Input: 5 -> 7 -> 5 -> 1 -> 7 -> NULL
Output: 2

Input: 5 -> 7 -> 8 -> 7 -> 1 -> NULL
Output: 1

Простой подход: мы пересекаем весь связанный список. Для каждого узла мы проверяем в оставшемся списке, существует ли дублирующий узел или нет. Если это так, то мы увеличиваем количество.

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

C ++

// C ++ реализация подхода
#include <iostream>
#include <unordered_set>

using namespace std;

  
// Представление узла

struct Node {

    int data;

    Node* next;

};

  

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

void insert(Node** head, int item)

{

    Node* temp = new Node();

    temp->data = item;

    temp->next = *head;

    *head = temp;

}

  
// Функция для подсчета количества
// дублировать узлы в связанном списке

int countNode(Node* head)

{

    int count = 0;

  

    while (head->next != NULL) {

  

        // Начиная со следующего узла

        Node *ptr = head->next;

        while (ptr != NULL) {

  

            // Если найден какой-то дублирующий узел

            if (head->data == ptr->data) {

                count++;

                break;

            }

            ptr = ptr->next;

        }

  

        head = head->next;

    }

  

    // Возвращаем количество повторяющихся узлов

    return count;

}

  
// Код драйвера

int main()

{

    Node* head = NULL;

    insert(&head, 5);

    insert(&head, 7);

    insert(&head, 5);

    insert(&head, 1);

    insert(&head, 7);

  

    cout << countNode(head);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

      
// Представление узла

static class Node 

    int data; 

    Node next; 

}; 

  

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

static Node insert(Node head, int item) 

    Node temp = new Node(); 

    temp.data = item; 

    temp.next = head; 

    head = temp;

    return head;

  
// Функция для подсчета количества
// дублировать узлы в связанном списке

static int countNode(Node head) 

    int count = 0

  

    while (head.next != null

    

  

        // Начиная со следующего узла

        Node ptr = head.next; 

        while (ptr != null

        

  

            // Если найден какой-то дублирующий узел

            if (head.data == ptr.data) 

            

                count++; 

                break

            

            ptr = ptr.next; 

        

  

        head = head.next; 

    

  

    // Возвращаем количество повторяющихся узлов

    return count; 

  
// Код драйвера

public static void main(String args[])

    Node head = null

    head = insert(head, 5); 

    head = insert(head, 7); 

    head = insert(head, 5); 

    head = insert(head, 1); 

    head = insert(head, 7); 

  

    System.out.println( countNode(head)); 

}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 реализация подхода

import math

  
# Представление узла

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.next = None

  
# Функция нажать на узел в начале

def push(head, item): 

    temp = Node(item); 

    temp.data = item; 

    temp.next = head; 

    head = temp;

    return head;

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

def countNode(head):

    count = 0

    while (head.next != None):

          

        # печать (1)

        # Начиная со следующего узла

        ptr = head.next

        while (ptr != None):

              

            # печать (2)

            # Если найден какой-то дублирующий узел

            if (head.data == ptr.data):

                count = count + 1

                break

            ptr = ptr.next

        head = head.next

          

    # Вернуть количество дублированных узлов

    return count

  
# Код драйвера

if __name__=='__main__'

  

    head = None;

    head = push(head, 5)

    head = push(head, 7)

    head = push(head, 5)

    head = push(head, 1)

    head = push(head, 7)

    print(countNode(head))

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

C #

// C # реализация подхода

using System;

      

class GFG

{

      
// Представление узла

public class Node 

    public int data; 

    public Node next; 

}; 

  

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

static Node insert(Node head, int item) 

    Node temp = new Node(); 

    temp.data = item; 

    temp.next = head; 

    head = temp;

    return head;

  
// Функция для подсчета количества
// дублировать узлы в связанном списке

static int countNode(Node head) 

    int count = 0; 

  

    while (head.next != null

    

  

        // Начиная со следующего узла

        Node ptr = head.next; 

        while (ptr != null

        

  

            // Если найден какой-то дублирующий узел

            if (head.data == ptr.data) 

            

                count++; 

                break

            

            ptr = ptr.next; 

        

  

        head = head.next; 

    

  

    // Возвращаем количество повторяющихся узлов

    return count; 

  
// Код драйвера

public static void Main(String []args)

    Node head = null

    head = insert(head, 5); 

    head = insert(head, 7); 

    head = insert(head, 5); 

    head = insert(head, 1); 

    head = insert(head, 7); 

  

    Console.WriteLine( countNode(head)); 

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

2

Сложность времени: O (n * n)

Эффективный подход: идея заключается в использовании хеширования

C ++

// C ++ реализация подхода
#include <iostream>
#include <unordered_set>

using namespace std;

  
// Представление узла

struct Node {

    int data;

    Node* next;

};

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

void insert(Node** head, int item)

{

    Node* temp = new Node();

    temp->data = item;

    temp->next = *head;

    *head = temp;

}

  
// Функция для подсчета количества
// дублировать узлы в связанном списке

int countNode(Node* head)

{

    if (head == NULL)

       return 0;;

  

    // Создать головку вставки хеш-таблицы

    unordered_set<int> s;

    s.insert(head->data);

  

    // Пройти через оставшиеся узлы

    int count = 0;

    for (Node *curr=head->next; curr != NULL; curr=curr->next) {

        if (s.find(curr->data) != s.end())

             count++; 

  

        s.insert(curr->data);

    }

  

    // Возвращаем количество повторяющихся узлов

    return count;

}

  
// Код драйвера

int main()

{

    Node* head = NULL;

    insert(&head, 5);

    insert(&head, 7);

    insert(&head, 5);

    insert(&head, 1);

    insert(&head, 7);

  

    cout << countNode(head);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.HashSet;

  

class GFG 

{

  
// Представление узла

static class Node

{

    int data;

    Node next;

};

static Node head;

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

static void insert(Node ref_head, int item)

{

    Node temp = new Node();

    temp.data = item;

    temp.next = ref_head;

    head = temp;

      
}

  
// Функция для подсчета количества
// дублировать узлы в связанном списке

static int countNode(Node head)

{

    if (head == null)

    return 0;;

  

    // Создать головку вставки хеш-таблицы

    HashSet<Integer>s = new HashSet<>();

    s.add(head.data);

  

    // Пройти через оставшиеся узлы

    int count = 0;

    for (Node curr=head.next; curr != null; curr=curr.next) 

    {

        if (s.contains(curr.data))

            count++; 

  

        s.add(curr.data);

    }

  

    // Возвращаем количество повторяющихся узлов

    return count;

}

  
// Код драйвера

public static void main(String[] args) 

{

  

    insert(head, 5);

    insert(head, 7);

    insert(head, 5);

    insert(head, 1);

    insert(head, 7);

  

    System.out.println(countNode(head));

}
}

  
// Этот код предоставлен Принчи Сингхом

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

      

class GFG 

{

  
// Представление узла

public class Node

{

    public int data;

    public Node next;

};

static Node head;

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

static void insert(Node ref_head, int item)

{

    Node temp = new Node();

    temp.data = item;

    temp.next = ref_head;

    head = temp;

      
}

  
// Функция для подсчета количества
// дублировать узлы в связанном списке

static int countNode(Node head)

{

    if (head == null)

    return 0;;

  

    // Создать головку вставки хеш-таблицы

    HashSet<int>s = new HashSet<int>();

    s.Add(head.data);

  

    // Пройти через оставшиеся узлы

    int count = 0;

    for (Node curr=head.next; curr != null; curr=curr.next) 

    {

        if (s.Contains(curr.data))

            count++; 

  

        s.Add(curr.data);

    }

  

    // Возвращаем количество повторяющихся узлов

    return count;

}

  
// Код драйвера

public static void Main(String[] args) 

{

  

    insert(head, 5);

    insert(head, 7);

    insert(head, 5);

    insert(head, 1);

    insert(head, 7);

  

    Console.WriteLine(countNode(head));

}
}

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

Выход:

2

Сложность времени: O (n)

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

Подсчет дубликатов в заданном связанном списке

0.00 (0%) 0 votes