Рубрики

Удалить все вхождения данного ключа в связанном списке

Имея односвязный список, удалите все вхождения данного ключа в нем. Например, рассмотрим следующий список.

Input: 2 -> 2 -> 1 -> 8 -> 2 ->  3 ->  2 -> 7
       Key to delete = 2
Output:  1 -> 8 -> 3 -> 7 

Это в основном расширение этого поста, которое удаляет первое вхождение данного ключа .

Нам нужно сначала проверить все вхождения в головном узле и соответствующим образом изменить головной узел. Затем нам нужно проверить все вхождения внутри цикла и удалить их одно за другим. Ниже приводится реализация для того же.

С

// C Программа для удаления всех вхождений данного ключа в связанном списке
#include <stdio.h>
#include <stdlib.h>

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

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Дана ссылка (указатель на указатель) на заголовок списка

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

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 deleteKey(struct Node **head_ref, int key)

{

    // Сохранить головной узел

    struct Node* temp = *head_ref, *prev;

  

    // Если головной узел сам содержит ключ или несколько вхождений ключа

    while (temp != NULL && temp->data == key)

    {

        *head_ref = temp->next;   // Измененная голова

        free(temp);               // свободная старая голова

        temp = *head_ref;         // Изменить темп

    }

  

    // Удалить вхождения, кроме головы

    while (temp != NULL)

    {

        // Поиск ключа для удаления, отслеживание

        // предыдущий узел, так как нам нужно изменить 'prev-> next'

        while (temp != NULL && temp->data != key)

        {

            prev = temp;

            temp = temp->next;

        }

  

        // Если ключ не присутствовал в связанном списке

        if (temp == NULL) return;

  

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

        prev->next = temp->next;

  

        free(temp);  // Свободная память

  

        // Обновляем Temp для следующей итерации внешнего цикла

        temp = prev->next;

    }

}

  
// Эта функция печатает содержимое связанного списка, начиная с
// данный узел

void printList(struct Node *node)

{

    while (node != NULL)

    {

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

        node = node->next;

    }

}

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

int main()

{

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

    struct Node* head = NULL;

  

    push(&head, 7);

    push(&head, 2);

    push(&head, 3);

    push(&head, 2);

    push(&head, 8);

    push(&head, 1);

    push(&head, 2);

    push(&head, 2);

  

    int key = 2; // ключ для удаления

  

    puts("Created Linked List: ");

    printList(head);

  

    deleteKey(&head, key);

    puts("\nLinked List after Deletion of 1: ");

  

    printList(head);

    return 0;

}

Джава

// Java-программа для удаления всех вхождений
// данного ключа в связанном списке

class LinkedList 

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

  

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

    class Node 

    

        int data; 

        Node next; 

        Node(int d) 

        

            data = d; 

            next = null

        

    

  

    / * Учитывая ключ, удаляет все вхождения

    данного ключа в связанном списке * /

    void deleteKey(int key) 

    

        // Сохранить головной узел

        Node temp = head, prev = null

      

        // Если главный узел сам содержит ключ

        // или несколько вхождений ключа

        while (temp != null && temp.data == key) 

        

            head = temp.next; // Измененная голова

            temp = head;         // Изменить темп

        

      

        // Удалить вхождения, кроме головы

        while (temp != null

        

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

            // отслеживаем предыдущий узел

            // как нам нужно изменить 'prev-> next'

            while (temp != null && temp.data != key) 

            

                prev = temp; 

                temp = temp.next; 

            

      

            // Если ключ не присутствовал в связанном списке

            if (temp == null) return

      

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

            prev.next = temp.next; 

      

            // Обновляем Temp для следующей итерации внешнего цикла

            temp = prev.next; 

        

    

  

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

    public void push(int new_data) 

    

        Node new_node = new Node(new_data); 

        new_node.next = head; 

        head = new_node; 

    

  

    / * Эта функция печатает содержимое связанного списка

    начиная с данного узла * /

    public void printList() 

    

        Node tnode = head; 

        while (tnode != null

        

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

            tnode = tnode.next; 

        

    

  

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

    public static void main(String[] args) 

    

        LinkedList llist = new LinkedList(); 

  

        llist.push(7); 

        llist.push(2); 

        llist.push(3); 

        llist.push(2);

        llist.push(8); 

        llist.push(1); 

        llist.push(2); 

        llist.push(2);

  

        int key = 2; // ключ для удаления

  

        System.out.println("Created Linked list is:"); 

        llist.printList(); 

  

        llist.deleteKey(key);

  

        System.out.println("\nLinked List after Deletion is:"); 

        llist.printList(); 

    

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

python3

# Python3 программа для удаления всех вхождений
# данного ключа в связанном списке

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

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.next = None

  
# Дана ссылка (указатель на указатель)
# в начало списка и int,
# вставляет новый узел в начало списка.

def push(head_ref, new_data):

    new_node = Node(0)

    new_node.data = new_data

    new_node.next = (head_ref)

    (head_ref) = new_node

    return head_ref

  
# Дана ссылка (указатель на указатель)
# к началу списка и ключу,
# удаляет все вхождения данного ключа
# в связанном списке

def deleteKey(head_ref, key):

      

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

    temp = head_ref

    prev = None

  

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

    # или несколько вхождений ключа

    while (temp != None and temp.data == key):

        head_ref = temp.next # Измененная голова

        temp = head_ref         # Изменить темп

      

    # Удалить вхождения, кроме головы

    while (temp != None):

          

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

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

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

        while (temp != None and temp.data != key):

            prev = temp

            temp = temp.next

          

        # Если ключ не присутствовал в связанном списке

        if (temp == None):

            return head_ref

  

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

        prev.next = temp.next

  

        # Обновление Temp для следующей итерации внешнего цикла

        temp = prev.next

        return head_ref

      
# Эта функция печатает содержимое связанного списка
# начиная с данного узла

def printList(node):

    while (node != None):

        print(node.data, end = " ")

        node = node.next

      
Код водителя

if __name__=='__main__'

      

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

    head = None

  

    head = push(head, 7)

    head = push(head, 2)

    head = push(head, 3)

    head = push(head, 2)

    head = push(head, 8)

    head = push(head, 1)

    head = push(head, 2)

    head = push(head, 2)

  

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

  

    print("Created Linked List: ")

    printList(head)

      

    head = deleteKey(head, key)

    print("\nLinked List after Deletion of 1: ")

  

    printList(head)

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

C #

// C # Программа для удаления всех вхождений
// данного ключа в связанном списке

using System;

  

class GFG 

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

  

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

    public class Node 

    

        public int data; 

        public Node next; 

        public Node(int d) 

        

            data = d; 

            next = null

        

    

  

    / * Учитывая ключ, удаляет все вхождения

    данного ключа в связанном списке * /

    void deleteKey(int key) 

    

        // Сохранить головной узел

        Node temp = head, prev = null

      

        // Если главный узел сам содержит ключ

        // или несколько вхождений ключа

        while (temp != null && temp.data == key) 

        

            head = temp.next; // Измененная голова

            temp = head;      // Изменить темп

        

      

        // Удалить вхождения, кроме головы

        while (temp != null

        

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

            // отслеживаем предыдущий узел

            // как нам нужно изменить 'prev-> next'

            while (temp != null && temp.data != key) 

            

                prev = temp; 

                temp = temp.next; 

            

      

            // Если ключ не присутствовал в связанном списке

            if (temp == null) return

      

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

            prev.next = temp.next; 

      

            // Обновляем Temp для следующей итерации внешнего цикла

            temp = prev.next; 

        

    

  

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

    public void Push(int new_data) 

    

        Node new_node = new Node(new_data); 

        new_node.next = head; 

        head = new_node; 

    

  

    / * Эта функция печатает содержимое связанного списка

    начиная с данного узла * /

    public void printList() 

    

        Node tnode = head; 

        while (tnode != null

        

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

            tnode = tnode.next; 

        

    

  

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

    public static void Main(String[] args) 

    

        GFG llist = new GFG(); 

  

        llist.Push(7); 

        llist.Push(2); 

        llist.Push(3); 

        llist.Push(2);

        llist.Push(8); 

        llist.Push(1); 

        llist.Push(2); 

        llist.Push(2);

  

        int key = 2; // ключ для удаления

  

        Console.WriteLine("Created Linked list is:"); 

        llist.printList(); 

  

        llist.deleteKey(key);

  

        Console.WriteLine("\nLinked List after Deletion is:"); 

        llist.printList(); 

    

}

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

Выход:

Created Linked List:
 2  2  1  8  2  3  2  7
Linked List after Deletion of 1:
 1  8  3  7 

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

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

Удалить все вхождения данного ключа в связанном списке

0.00 (0%) 0 votes