Рубрики

Удалить дубликаты из несортированного связанного списка

Напишите функцию removeDuplicates (), которая берет список и удаляет все дублирующиеся узлы из списка. Список не отсортирован.

Например, если связанный список 12-> 11-> 12-> 21-> 41-> 43-> 21, то removeDuplicates () должен преобразовать список в 12-> 11-> 21-> 41-> 43.

МЕТОД 1 (Использование двух циклов)
Это простой способ, где используются две петли. Внешний цикл используется для выбора элементов один за другим, а внутренний цикл сравнивает выбранный элемент с остальными элементами.

Спасибо Гаураву Саксене за помощь в написании этого кода.

C ++

/ * Программа для удаления дубликатов в несортированном

   связанный список * /

#include<bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    struct Node *next;

};

  
// Сервисная функция для создания нового узла

struct Node *newNode(int data)

{

   Node *temp = new Node;

   temp->data = data;

   temp->next = NULL;

   return temp;

}

  
/ * Функция удаления дубликатов из

   несортированный связанный список * /

void removeDuplicates(struct Node *start)

{

    struct Node *ptr1, *ptr2, *dup;

    ptr1 = start;

  

    / * Выбрать элементы один за другим * /

    while (ptr1 != NULL && ptr1->next != NULL)

    {

        ptr2 = ptr1;

  

        / * Сравните выбранный элемент с отдыхом

           элементов * /

        while (ptr2->next != NULL)

        {

            / * Если дубликат, то удалить его * /

            if (ptr1->data == ptr2->next->data)

            {

                / * здесь важна последовательность шагов * /

                dup = ptr2->next;

                ptr2->next = ptr2->next->next;

                delete(dup);

            }

            else / * Это сложно * /

                ptr2 = ptr2->next;

        }

        ptr1 = ptr1->next;

    }

}

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

void printList(struct Node *node)

{

    while (node != NULL)

    {

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

        node = node->next;

    }

}

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

int main()

{

    / * Составленный связанный список:

     10-> 12-> 11-> 11-> 12-> 11-> 10 * /

    struct Node *start = newNode(10);

    start->next = newNode(12);

    start->next->next = newNode(11);

    start->next->next->next = newNode(11);

    start->next->next->next->next = newNode(12);

    start->next->next->next->next->next =

                                    newNode(11);

    start->next->next->next->next->next->next =

                                    newNode(10);

  

    printf("Linked list before removing duplicates ");

    printList(start);

  

    removeDuplicates(start);

  

    printf("\nLinked list after removing duplicates ");

    printList(start);

  

    return 0;

}

Джава

// Java программа для удаления дубликатов из несортированных
// связанный список

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    / * Функция удаления дубликатов из

       несортированный связанный список * /

    void remove_duplicates() {

        Node ptr1 = null, ptr2 = null, dup = null;

        ptr1 = head;

  

        / * Выбрать элементы один за другим * /

        while (ptr1 != null && ptr1.next != null) {

            ptr2 = ptr1;

  

            / * Сравните выбранный элемент с отдыхом

                элементов * /

            while (ptr2.next != null) {

  

                / * Если дубликат, то удалить его * /

                if (ptr1.data == ptr2.next.data) {

  

                    / * здесь важна последовательность шагов * /

                    dup = ptr2.next;

                    ptr2.next = ptr2.next.next;

                    System.gc();

                } else / * Это сложно * / {

                    ptr2 = ptr2.next;

                }

            }

            ptr1 = ptr1.next;

        }

    }

  

    void printList(Node node) {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.head = new Node(10);

        list.head.next = new Node(12);

        list.head.next.next = new Node(11);

        list.head.next.next.next = new Node(11);

        list.head.next.next.next.next = new Node(12);

        list.head.next.next.next.next.next = new Node(11);

        list.head.next.next.next.next.next.next = new Node(10);

  

        System.out.println("Linked List before removing duplicates : \n ");

        list.printList(head);

  

        list.remove_duplicates();

        System.out.println("");

        System.out.println("Linked List after removing duplicates : \n ");

        list.printList(head);

    }

}
// Этот код предоставлен Mayank Jaiswal


Выход :

Linked list before removing duplicates:
 10 12 11 11 12 11 10 
Linked list after removing duplicates:
 10 12 11 

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

МЕТОД 2 (использовать сортировку)
В общем, Merge Sort — это наиболее подходящий алгоритм сортировки для эффективной сортировки связанных списков.
1) Сортировка элементов с использованием Merge Sort. Скоро мы напишем пост о сортировке связанного списка. O (NlogN)
2) Удалить дубликаты за линейное время, используя алгоритм удаления дубликатов в отсортированном связанном списке. На)

Обратите внимание, что этот метод не сохраняет первоначальный порядок элементов.

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

МЕТОД 3 (использовать хеширование)
Мы пересекаем список ссылок от головы до конца. Для каждого вновь обнаруженного элемента мы проверяем, есть ли он в хеш-таблице: если да, мы удаляем его; иначе мы помещаем это в хэш-таблицу.

C ++

/ * Программа для удаления дубликатов в несортированном

   связанный список * /

#include<bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    struct Node *next;

};

  
// Сервисная функция для создания нового узла

struct Node *newNode(int data)

{

   Node *temp = new Node;

   temp->data = data;

   temp->next = NULL;

   return temp;

}

  
/ * Функция удаления дубликатов из

   несортированный связанный список * /

void removeDuplicates(struct Node *start)

{

    // Хеш для хранения увиденных значений

    unordered_set<int> seen;

  

    / * Выбрать элементы один за другим * /

    struct Node *curr = start;

    struct Node *prev = NULL;

    while (curr != NULL)

    {

        // Если текущее значение видно раньше

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

        {

           prev->next = curr->next;

           delete (curr);

        }

        else

        {

           seen.insert(curr->data);

           prev = curr;

        }

        curr = prev->next;

    }

}

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

void printList(struct Node *node)

{

    while (node != NULL)

    {

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

        node = node->next;

    }

}

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

int main()

{

    / * Составленный связанный список:

     10-> 12-> 11-> 11-> 12-> 11-> 10 * /

    struct Node *start = newNode(10);

    start->next = newNode(12);

    start->next->next = newNode(11);

    start->next->next->next = newNode(11);

    start->next->next->next->next = newNode(12);

    start->next->next->next->next->next =

                                    newNode(11);

    start->next->next->next->next->next->next =

                                    newNode(10);

  

    printf("Linked list before removing duplicates : \n");

    printList(start);

  

    removeDuplicates(start);

  

    printf("\nLinked list after removing duplicates : \n");

    printList(start);

  

    return 0;

}

Джава

// Java программа для удаления дубликатов
// из несортированного связанного списка

  

import java.util.HashSet;

  

public class removeDuplicates 

{

    static class node 

    {

        int val;

        node next;

  

        public node(int val) 

        {

            this.val = val;

        }

    }

      

    / * Функция удаления дубликатов из

       несортированный связанный список * /

    static void removeDuplicate(node head) 

    {

        // Хеш для хранения увиденных значений

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

      

        / * Выбрать элементы один за другим * /

        node current = head;

        node prev = null;

        while (current != null

        {

            int curval = current.val;

              

             // Если текущее значение видно раньше

            if (hs.contains(curval)) {

                prev.next = current.next;

            } else {

                hs.add(curval);

                prev = current;

            }

            current = current.next;

        }

  

    }

      

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

    static void printList(node head) 

    {

        while (head != null

        {

            System.out.print(head.val + " ");

            head = head.next;

        }

    }

  

    public static void main(String[] args) 

    {

        / * Составленный связанный список:

         10-> 12-> 11-> 11-> 12-> 11-> 10 * /

        node start = new node(10);

        start.next = new node(12);

        start.next.next = new node(11);

        start.next.next.next = new node(11);

        start.next.next.next.next = new node(12);

        start.next.next.next.next.next = new node(11);

        start.next.next.next.next.next.next = new node(10);

  

        System.out.println("Linked list before removing duplicates :");

        printList(start);

  

        removeDuplicate(start);

  

        System.out.println("\nLinked list after removing duplicates :");

        printList(start);

    }

}

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


Выход :

Linked list before removing duplicates:
 10 12 11 11 12 11 10 
Linked list after removing duplicates:
 10 12 11 

Спасибо Bearwang за предложение этого метода.

Сложность времени: в среднем O (n) (при условии, что время доступа к хеш-таблице в среднем равно O (1)).

Пожалуйста, пишите комментарии, если вы обнаружите, что какое-либо из приведенных выше объяснений / алгоритмов неверно или есть лучшие способы решения той же проблемы.

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

Удалить дубликаты из несортированного связанного списка

0.00 (0%) 0 votes