Рубрики

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

Напишите функцию, которая берет список, отсортированный в неубывающем порядке, и удаляет все дублирующиеся узлы из списка. Список должен быть пройден только один раз.

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

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

Реализация:
Функции, отличные от removeDuplicates (), предназначены только для создания связанного связанного списка и проверки removeDuplicates ().

C ++

/ * C ++ Программа для удаления дубликатов из отсортированного связанного списка * /
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node* next; 

}; 

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

void removeDuplicates(Node* head) 

    / * Указатель для просмотра связанного списка * /

    Node* current = head; 

  

    / * Указатель для хранения следующего указателя узла, который будет удален * /

    Node* next_next; 

      

    / * ничего не делать, если список пуст * /

    if (current == NULL) 

    return

  

    / * Просматривать список до последнего узла * /

    while (current->next != NULL) 

    

    / * Сравнить текущий узел со следующим узлом * /

    if (current->data == current->next->data) 

    

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

        next_next = current->next->next; 

        free(current->next); 

        current->next = next_next; 

    

    else / * Это сложно: только вперед, если нет удаления * /

    

        current = current->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; 

    

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

int main() 

    / * Начнем с пустого списка * /

    Node* head = NULL; 

      

    / * Давайте создадим отсортированный связанный список для проверки функций

    Созданный связанный список будет 11-> 11-> 11-> 13-> 13-> 20 * /

    push(&head, 20); 

    push(&head, 13); 

    push(&head, 13); 

    push(&head, 11); 

    push(&head, 11); 

    push(&head, 11);                                     

  

    cout<<"Linked list before duplicate removal "

    printList(head); 

  

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

    removeDuplicates(head); 

  

    cout<<"\nLinked list after duplicate removal ";     

    printList(head);             

      

    return 0; 

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

С

/ * C Программа для удаления дубликатов из отсортированного связанного списка * /
#include<stdio.h>
#include<stdlib.h>

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

struct Node

{

    int data;

    struct Node* next;

};

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

void removeDuplicates(struct Node* head)

{

    / * Указатель для просмотра связанного списка * /

    struct Node* current = head;

  

    / * Указатель для хранения следующего указателя узла, который будет удален * /

    struct Node* next_next; 

    

    / * ничего не делать, если список пуст * /

    if (current == NULL) 

       return

  

    / * Просматривать список до последнего узла * /

    while (current->next != NULL) 

    {

       / * Сравнить текущий узел со следующим узлом * /

       if (current->data == current->next->data) 

       {

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

           next_next = current->next->next;

           free(current->next);

           current->next = next_next;  

       }

       else / * Это сложно: только вперед, если нет удаления * /

       {

          current = current->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;

    }

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

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

    

    / * Давайте создадим отсортированный связанный список для проверки функций

     Созданный связанный список будет 11-> 11-> 11-> 13-> 13-> 20 * /

    push(&head, 20);

    push(&head, 13);

    push(&head, 13);  

    push(&head, 11);

    push(&head, 11);

    push(&head, 11);                                    

  

    printf("\n Linked list before duplicate removal  ");

    printList(head); 

  

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

    removeDuplicates(head); 

  

    printf("\n Linked list after duplicate removal ");         

    printList(head);            

    

    return 0;

}

Джава

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

class LinkedList

{

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

   

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

    class Node

    {

        int data;

        Node next;

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

    }

  

    void removeDuplicates()

    {

        / * Еще одна ссылка на голову * /

        Node curr = head;

  

        / * Перемещение по списку до последнего узла * /

        while (curr != null) {

             Node temp = curr;

            / * Сравнить текущий узел со следующим узлом и

            продолжайте удалять их, пока они не будут соответствовать текущим

            данные узла * /

            while(temp!=null && temp.data==curr.data) {

                temp = temp.next;

            }

            / * Установить текущий узел рядом со следующим другим

            элемент, обозначаемый как temp * /

            curr.next = temp;

            curr = curr.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();

        llist.push(20);

        llist.push(13);

        llist.push(13);

        llist.push(11);

        llist.push(11);

        llist.push(11);

          

        System.out.println("List before removal of duplicates");

        llist.printList();

          

        llist.removeDuplicates();

          

        System.out.println("List after removal of elements");

        llist.printList();

    }

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

Python 3

# Python3 программа для удаления дубликатов
# узлы из отсортированного связанного списка

  
# Класс узла

class Node: 

  

    # Конструктор для инициализации

    # объект узла

    def __init__(self, data): 

        self.data = data 

        self.next = None

  

class LinkedList: 

  

    # Функция для инициализации головы

    def __init__(self): 

        self.head = None

  

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

    # с начала

    def push(self, new_data): 

        new_node = Node(new_data) 

        new_node.next = self.head 

        self.head = new_node 

  

    # Учитывая ссылку на главу

    # список и ключ, удали первый

    # вхождение ключа в связанный список

    def deleteNode(self, key): 

          

        # Хранить головной узел

        temp = self.head 

  

        # Если головной узел сам содержит

        # ключ для удаления

        if (temp is not None): 

            if (temp.data == key): 

                self.head = temp.next

                temp = None

                return

  

        # Поиск ключа, который нужно удалить,

        # отслеживать предыдущий узел как

        # нам нужно изменить 'prev.next'

        while(temp is not None): 

            if temp.data == key: 

                break

            prev = temp 

            temp = temp.next

  

        # если ключа не было в

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

        if(temp == None): 

            return

  

        # Отключить узел от связанного списка

        prev.next = temp.next

  

        temp = None

  

    # Утилита для печати

    # связанный LinkedList

    def printList(self): 

        temp = self.head 

        while(temp): 

            print(temp.data , end = ' ')

            temp = temp.next

      

    # Эта функция удаляет дубликаты

    # из отсортированного списка

    def removeDuplicates(self):

        temp = self.head

        if temp is None:

            return

        while temp.next is not None:

            if temp.data == temp.next.data:

                new = temp.next.next

                temp.next = None

                temp.next = new

            else:

                temp = temp.next

        return self.head

  
Код водителя

llist = LinkedList() 

  

llist.push(20

llist.push(13

llist.push(13)

llist.push(11)

llist.push(11)

llist.push(11)

print ("Created Linked List: ")

llist.printList() 

print()

print("Linked List after removing"

             "duplicate elements:")

llist.removeDuplicates()
llist.printList() 

  
# Этот код предоставлен
# Душянт Патхак.

C #

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

using System;

      

public class LinkedList

{

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

  

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

    class Node

    {

        public int data;

        public Node next;

        public Node(int d) 

        {

            data = d; next = null;

        }

    }

  

    void removeDuplicates()

    {

        / * Еще одна ссылка на голову * /

        Node current = head;

  

        / * Указатель для хранения следующего

        указатель удаляемого узла * /

        Node next_next;

  

        / * ничего не делать, если список пуст * /

        if (head == null

            return;

  

        / * Перемещение по списку до последнего узла * /

        while (current.next != null

        {

  

            / * Сравнить текущий узел со следующим узлом * /

            if (current.data == current.next.data) 

            {

                next_next = current.next.next;

                current.next = null;

                current.next = next_next;

            }

            else // аванс, если нет удаления

                current = current.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();

        llist.push(20);

        llist.push(13);

        llist.push(13);

        llist.push(11);

        llist.push(11);

        llist.push(11);

          

        Console.WriteLine("List before removal of duplicates");

        llist.printList();

          

        llist.removeDuplicates();

          

        Console.WriteLine("List after removal of elements");

        llist.printList();

    }

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


Выход:

 Linked list before duplicate removal 11 11 11 13 13 20 
 Linked list after duplicate removal 11 13 20 


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

Рекурсивный подход:

C ++

/ * C ++ Программа для удаления дубликатов из отсортированного связанного списка * /
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node* next; 

}; 

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

void removeDuplicates(Node* head) 

    / * Указатель для хранения указателя удаляемого узла * /

    Node* to_free; 

      

    / * ничего не делать, если список пуст * /

    if (head == NULL) 

        return

  

    / * Просматривать список до последнего узла * /

    if (head->next != NULL) 

    

          

        / * Сравнить головной узел со следующим узлом * /

        if (head->data == head->next->data) 

        

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

              указатель to_free хранит следующий заголовок

             указатель, который нужно удалить. * /    

            to_free = head->next; 

        head->next = head->next->next;

        free(to_free);

        removeDuplicates(head);

        

        else / * Это сложно: только вперед, если нет удаления * /

        

            removeDuplicates(head->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; 

    

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

int main() 

    / * Начнем с пустого списка * /

    Node* head = NULL; 

      

    / * Давайте создадим отсортированный связанный список для проверки функций

    Созданный связанный список будет 11-> 11-> 11-> 13-> 13-> 20 * /

    push(&head, 20); 

    push(&head, 13); 

    push(&head, 13); 

    push(&head, 11); 

    push(&head, 11); 

    push(&head, 11);                                     

  

    cout<<"Linked list before duplicate removal "

    printList(head); 

  

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

    removeDuplicates(head); 

  

    cout<<"\nLinked list after duplicate removal ";     

    printList(head);             

      

    return 0; 

  
// Этот код предоставлен Ашита Гупта

С

/ * C рекурсивная программа для удаления дубликатов из отсортированного связанного списка * /
#include<stdio.h>
#include<stdlib.h>

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

struct Node

{

    int data;

    struct Node* 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;

    }

  

 Node* deleteDuplicates(Node* head) {

        if (head == nullptr) return nullptr;

        if (head->next == nullptr) return head;

  

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

            Node *tmp;

            // Если найти следующий элемент дубликат, сохранить следующий указатель для удаления,

            // пропустить его, а затем удалить сохраненный. Возврат головы

            tmp = head->next;

            head->next = head->next->next;

            free(tmp);

            return deleteDuplicates(head);

        }

  

        else {

  

            // если следующий элемент не найден дубликатом, оставим голову

            // и проверка из следующего элемента

            head->next = deleteDuplicates(head->next);

            return head;

        }

    }

  

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

    

    / * Давайте создадим отсортированный связанный список для проверки функций

     Созданный связанный список будет 11-> 11-> 11-> 13-> 13-> 20 * /

    push(&head, 20);

    push(&head, 13);

    push(&head, 13);  

    push(&head, 11);

    push(&head, 11);

    push(&head, 11);                                    

  

    printf("\n Linked list before duplicate removal  ");

    printList(head); 

  

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

    head = deleteDuplicates(head); 

  

    printf("\n Linked list after duplicate removal ");         

    printList(head);            

    

    return 0;

}

/ * Этот код предоставлен Йогеш Шукла * /   

Джава

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

class GFG

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

static class Node 

    int data; 

    Node next; 

}; 

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

static Node removeDuplicates(Node head) 

    / * Указатель для хранения указателя

    удаляемого узла * /

    Node to_free; 

      

    / * ничего не делать, если список пуст * /

    if (head == null

        return null

  

    / * Просматривать список до последнего узла * /

    if (head.next != null

    

          

        / * Сравнить головной узел со следующим узлом * /

        if (head.data == head.next.data) 

        

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

            указатель to_free хранит следующий заголовок

            указатель, который нужно удалить. * /

            to_free = head.next; 

            head.next = head.next.next;

            removeDuplicates(head);

        

          

        / * Это сложно: только вперед, если нет удаления * /

        else 

        

            removeDuplicates(head.next);

        

    

    return head;

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла в begeing
связанного списка * /

static Node 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; 

    return head_ref;

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

static void printList(Node node) 

    while (node != null

    

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

        node = node.next; 

    

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

public static void main(String args[])

    / * Начнем с пустого списка * /

    Node head = null

      

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

    проверить функции

    Созданный связанный список будет 11.11.11.13.13.20 * /

    head = push(head, 20); 

    head = push(head, 13); 

    head = push(head, 13); 

    head = push(head, 11); 

    head = push(head, 11); 

    head = push(head, 11);                                     

  

    System.out.println("Linked list before"

                      " duplicate removal "); 

    printList(head); 

  

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

    head = removeDuplicates(head); 

  

    System.out.println("\nLinked list after"

                       " duplicate removal ");     

    printList(head);             

}
}  

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

python3

# Python3 Программа для удаления дубликатов
# из отсортированного связанного списка

import math

  
# Узел списка ссылок

class Node: 

    def __init__(self,data): 

        self.data = data 

        self.next = None

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

def removeDuplicates(head): 

      

    # Указатель для хранения указателя узла

    # подлежит удалению to_free

      

    # ничего не делать, если список пуст

    if (head == None): 

        return

  

    # Обход списка до последнего узла

    if (head.next != None): 

          

        # Сравнить головной узел со следующим узлом

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

              

            # Последовательность шагов важна.

            Указатель # to_free хранит следующий заголовок

            # указатель, который нужно удалить.

            to_free = head.next

            head.next = head.next.next

              

            # бесплатно (to_free)

            removeDuplicates(head) 

          

        # Это сложно: только вперед, если нет удаления

        else

            removeDuplicates(head.next

          

    return head

  
# ПОЛЕЗНЫЕ ФУНКЦИИ
# Функция для вставки узла в
# просмотр связанного списка

def push(head_ref, new_data): 

      

    # выделить узел

    new_node = Node(new_data) 

              

    # положить в данные

    new_node.data = new_data 

                  

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

    new_node.next = head_ref     

          

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

    head_ref = new_node

    return head_ref

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

def printList(node): 

    while (node != None): 

        print(node.data, end = " "

        node = node.next

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

if __name__=='__main__'

  

    # Начнем с пустого списка

    head = None

      

    # Давайте создадим отсортированный связанный список

    # для проверки функций

    # Создан связанный список будет 11.11.11.13.13.20

    head = push(head, 20

    head = push(head, 13

    head = push(head, 13

    head = push(head, 11

    head = push(head, 11

    head = push(head, 11)                                 

  

    print("Linked list before duplicate removal ",

                                         end = "") 

    printList(head) 

  

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

    removeDuplicates(head) 

  

    print("\nLinked list after duplicate removal ",

                                          end = "") 

    printList(head)         

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

C #

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

using System;

      

class GFG

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

public class Node 

    public int data; 

    public Node next; 

}; 

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

static Node removeDuplicates(Node head) 

    / * Указатель для хранения указателя

    удаляемого узла * /

    Node to_free; 

      

    / * ничего не делать, если список пуст * /

    if (head == null

        return null

  

    / * Просматривать список до последнего узла * /

    if (head.next != null

    

          

        / * Сравнить головной узел со следующим узлом * /

        if (head.data == head.next.data) 

        

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

            указатель to_free хранит следующий заголовок

            указатель, который нужно удалить. * /

            to_free = head.next; 

            head.next = head.next.next;

            removeDuplicates(head);

        

          

        / * Это сложно: только вперед, если нет удаления * /

        else

        

            removeDuplicates(head.next);

        

    

    return head;

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла в begeing
связанного списка * /

static Node 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; 

    return head_ref;

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

static void printList(Node node) 

    while (node != null

    

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

        node = node.next; 

    

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

public static void Main(String []args)

    / * Начнем с пустого списка * /

    Node head = null

      

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

    проверить функции

    Созданный связанный список будет 11.11.11.13.13.20 * /

    head = push(head, 20); 

    head = push(head, 13); 

    head = push(head, 13); 

    head = push(head, 11); 

    head = push(head, 11); 

    head = push(head, 11);                                     

  

    Console.Write("Linked list before"

                  " duplicate removal "); 

    printList(head); 

  

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

    head = removeDuplicates(head); 

  

    Console.Write("\nLinked list after"

                  " duplicate removal ");     

    printList(head);             

}
}

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


выход

Linked list before duplicate removal  11 11 11 13 13 20 
Linked list after duplicate removal 11 13 20 

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

Ссылки:
cslibrary.stanford.edu/105/LinkedListProblems.pdf

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

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

0.00 (0%) 0 votes