Рубрики

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

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

#include <stdio.h>
#include <stdlib.h>

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

struct Node {

    int data;

    struct Node* next;

};

  
// Функция для удаления последнего вхождения

void deleteLast(struct Node** head, int x)

{

        struct Node** tmp1 = NULL;

        while(*head) {

                if((*head)->data == x) {

                        tmp1 = head;

                }

                head = &(*head)->next;

        }

        if(tmp1) {

                struct Node* tmp = *tmp1;

                *tmp1 = tmp->next;

                free(tmp);

        }

}

  
/ * Утилита для создания нового узла с
данный ключ * /

struct Node* newNode(int x)

{

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

    node->data = x;

    node->next = NULL;

    return node;

}

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

void display(struct Node* head)

{

    struct Node* temp = head;

    if (head == NULL) {

        printf("NULL\n");

        return;

    }

    while (temp != NULL) {

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

        temp = temp->next;

    }

    printf("NULL\n");

}

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

int main()

{

    struct Node* head = newNode(1);

    head->next = newNode(2);

    head->next->next = newNode(3);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(5);

    head->next->next->next->next->next = newNode(4);

    head->next->next->next->next->next->next = newNode(4);

    printf("Created Linked list: ");

    display(head);

    deleteLast(&head, 4);   // Передаем адрес указателя головы

    printf("List after deletion of 4: ");

    display(head);

    return 0;

}

Приведен список избранного и ключ для удаления. Удалить последнее вхождение ключа из связанного. В списке могут быть дубликаты.

Примеры:

Input:   1->2->3->5->2->10, key = 2
Output:  1->2->3->5->10

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

C ++

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

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

struct Node {

    int key;

    struct Node* next;

};

  

void deleteLast(Node* head, int key)

{

    // Инициализируем предыдущий узел для удаления

    Node* x = NULL;

  

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

    // удалено

    Node* temp = head;

    while (temp) {

        // Если мы нашли ключ, обновляем xv

        if (temp->key == key)

            x = temp;

  

        temp = temp->next;

    }

  

    // ключ встречается хотя бы один раз

    if (x != NULL) {

  

        // Копируем ключ следующего узла в x

        x->key = x->next->key;

  

        // Сохранить и отменить связь далее

        temp = x->next;

        x->next = x->next->next;

  

        // Свободная память для следующего

        delete temp;

    }

}

  
/ * Утилита для создания нового узла с

   данный ключ * /

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

    temp->next = NULL;

    return temp;

}

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

void printList(struct Node* node)

{

    while (node != NULL) {

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

        node = node->next;

    }

}

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

int main()

{

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

    struct Node* head = newNode(1);

    head->next = newNode(2);

    head->next->next = newNode(3);

    head->next->next->next = newNode(5);

    head->next->next->next->next = newNode(2);

    head->next->next->next->next->next = newNode(10);

  

    puts("Created Linked List: ");

    printList(head);

    deleteLast(head, 2);

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

    printList(head);

    return 0;

}

Джава

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

class GFG

{

      

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

static class Node 

    int key; 

    Node next; 

}; 

  

static Node deleteLast(Node head, int key) 

    // Инициализируем предыдущий узел для удаления

    Node x = null

  

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

    // удалено

    Node temp = head; 

    while (temp != null

    

        // Если мы нашли ключ, обновляем xv

        if (temp.key == key) 

            x = temp; 

  

        temp = temp.next; 

    

  

    // ключ встречается хотя бы один раз

    if (x != null

    

  

        // Копируем ключ следующего узла в x

        x.key = x.next.key; 

  

        // Сохранить и отменить связь далее

        temp = x.next; 

        x.next = x.next.next; 

  

        // Свободная память для следующего

    

    return head;

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

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.key = key; 

    temp.next = null

    return temp; 

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

static void printList( Node node) 

    while (node != null

    

        System.out.printf(" %d ", node.key); 

        node = node.next; 

    

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

public static void main(String args[])

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

    Node head = newNode(1); 

    head.next = newNode(2); 

    head.next.next = newNode(3); 

    head.next.next.next = newNode(5); 

    head.next.next.next.next = newNode(2); 

    head.next.next.next.next.next = newNode(10); 

  

    System.out.printf("Created Linked List: "); 

    printList(head); 

    deleteLast(head, 2); 

    System.out.printf("\nLinked List after Deletion of 1: "); 

    printList(head); 

}

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

C #

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

using System;

  

class GFG 

      

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

public class Node 

    public int key; 

    public Node next; 

}; 

  

static Node deleteLast(Node head, int key) 

    // Инициализируем предыдущий узел для удаления

    Node x = null

  

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

    // удалено

    Node temp = head; 

    while (temp != null

    

        // Если мы нашли ключ, обновляем xv

        if (temp.key == key) 

            x = temp; 

  

        temp = temp.next; 

    

  

    // ключ встречается хотя бы один раз

    if (x != null

    

  

        // Копируем ключ следующего узла в x

        x.key = x.next.key; 

  

        // Сохранить и отменить связь далее

        temp = x.next; 

        x.next = x.next.next; 

  

        // Свободная память для следующего

    

    return head; 

  
/// Utility function to create a new node with 
// данный ключ /

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.key = key; 

    temp.next = null

    return temp; 

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

static void printList( Node node) 

    while (node != null

    

        Console.Write(" {0} ", node.key); 

        node = node.next; 

    

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

public static void Main(String []args) 

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

    Node head = newNode(1); 

    head.next = newNode(2); 

    head.next.next = newNode(3); 

    head.next.next.next = newNode(5); 

    head.next.next.next.next = newNode(2); 

    head.next.next.next.next.next = newNode(10); 

  

    Console.Write("Created Linked List: "); 

    printList(head); 

    deleteLast(head, 2); 

    Console.Write("\nLinked List after Deletion of 1: "); 

    printList(head); 


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


Выход:

Created Linked List: 
 1  2  3  5  2  10 
Linked List after Deletion of 1: 
 1  2  3  5  10

Приведенное выше решение не работает, когда удаляемый узел является последним узлом.

Следующее решение обрабатывает все случаи.

C ++

// AC программа для демонстрации удаления последней
// Узел в односвязном списке
#include <stdio.h>
#include <stdlib.h>

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

struct Node {

    int data;

    struct Node* next;

};

  
// Функция для удаления последнего вхождения

void deleteLast(struct Node* head, int x)

{

    struct Node *temp = head, *ptr = NULL;

    while (temp) {

  

        // Если найден ключ, обновить

        if (temp->data == x) 

            ptr = temp;        

        temp = temp->next;

    }

  

    // Если последнее вхождение является последним узлом

    if (ptr != NULL && ptr->next == NULL) {

        temp = head;

        while (temp->next != ptr) 

            temp = temp->next;       

        temp->next = NULL;

    }

  

    // Если это не последний узел

    if (ptr != NULL && ptr->next != NULL) {

        ptr->data = ptr->next->data;

        temp = ptr->next;

        ptr->next = ptr->next->next;

        free(temp);

    }

}

  
/ * Утилита для создания нового узла с
данный ключ * /

struct Node* newNode(int x)

{

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

    node->data = x;

    node->next = NULL;

    return node;

}

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

void display(struct Node* head)

{

    struct Node* temp = head;

    if (head == NULL) {

        printf("NULL\n");

        return;

    }

    while (temp != NULL) {

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

        temp = temp->next;

    }

    printf("NULL\n");

}

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

int main()

{

    struct Node* head = newNode(1);

    head->next = newNode(2);

    head->next->next = newNode(3);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(5);

    head->next->next->next->next->next = newNode(4);

    head->next->next->next->next->next->next = newNode(4);

    printf("Created Linked list: ");

    display(head);

    deleteLast(head, 4);

    printf("List after deletion of 4: ");

    display(head);

    return 0;

}

Джава

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

class GFG 

{

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

static class Node 

    int data; 

    Node next; 

}; 

  
// Функция для удаления последнего вхождения

static void deleteLast(Node head, int x) 

    Node temp = head, ptr = null

    while (temp!=null

    

  

        // Если найден ключ, обновить

        if (temp.data == x) 

            ptr = temp;     

        temp = temp.next; 

    

  

    // Если последнее вхождение является последним узлом

    if (ptr != null && ptr.next == null

    

        temp = head; 

        while (temp.next != ptr) 

            temp = temp.next; 

        temp.next = null

    

  

    // Если это не последний узел

    if (ptr != null && ptr.next != null)

    

        ptr.data = ptr.next.data; 

        temp = ptr.next; 

        ptr.next = ptr.next.next; 

        System.gc();

    

  
/ * Утилита для создания нового узла с
данный ключ * /

static Node newNode(int x) 

    Node node = new Node(); 

    node.data = x; 

    node.next = null

    return node; 

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

static void display(Node head) 

    Node temp = head; 

    if (head == null

    

        System.out.print("null\n"); 

        return

    

    while (temp != null

    

        System.out.printf("%d --> ", temp.data); 

        temp = temp.next; 

    

    System.out.print("null\n"); 

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

public static void main(String[] args) 

{

    Node head = newNode(1); 

    head.next = newNode(2); 

    head.next.next = newNode(3); 

    head.next.next.next = newNode(4); 

    head.next.next.next.next = newNode(5); 

    head.next.next.next.next.next = newNode(4); 

    head.next.next.next.next.next.next = newNode(4); 

    System.out.print("Created Linked list: "); 

    display(head); 

    deleteLast(head, 4); 

    System.out.print("List after deletion of 4: "); 

    display(head); 

}
}

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

C #

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

using System;

  

class GFG 

{

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

public class Node 

    public int data; 

    public Node next; 

}; 

  
// Функция для удаления последнего вхождения

static void deleteLast(Node head, int x) 

    Node temp = head, ptr = null

    while (temp != null

    

  

        // Если найден ключ, обновить

        if (temp.data == x) 

            ptr = temp;     

        temp = temp.next; 

    

  

    // Если последнее вхождение является последним узлом

    if (ptr != null && ptr.next == null

    

        temp = head; 

        while (temp.next != ptr) 

            temp = temp.next; 

        temp.next = null

    

  

    // Если это не последний узел

    if (ptr != null && ptr.next != null)

    

        ptr.data = ptr.next.data; 

        temp = ptr.next; 

        ptr.next = ptr.next.next; 

    

  
/ * Утилита для создания нового узла с
данный ключ * /

static Node newNode(int x) 

    Node node = new Node(); 

    node.data = x; 

    node.next = null

    return node; 

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

static void display(Node head) 

    Node temp = head; 

    if (head == null

    

        Console.Write("null\n"); 

        return

    

    while (temp != null

    

        Console.Write("{0} --> ", temp.data); 

        temp = temp.next; 

    

    Console.Write("null\n"); 

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

public static void Main(String[] args) 

{

    Node head = newNode(1); 

    head.next = newNode(2); 

    head.next.next = newNode(3); 

    head.next.next.next = newNode(4); 

    head.next.next.next.next = newNode(5); 

    head.next.next.next.next.next = newNode(4); 

    head.next.next.next.next.next.next = newNode(4); 

    Console.Write("Created Linked list: "); 

    display(head); 

    deleteLast(head, 4); 

    Console.Write("List after deletion of 4: "); 

    display(head); 

}
}

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

Выход:

Created Linked List: 
 1  2  3  4  5  4  4 
Linked List after Deletion of 1: 
 1  2  3  4  5  4

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

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

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

0.00 (0%) 0 votes