Рубрики

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

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

Имея односвязный список, напишите функцию для удаления данного узла. Ваша функция должна соответствовать следующим ограничениям:
1) Он должен принять указатель на начальный узел в качестве первого параметра, а узел должен быть удален в качестве второго параметра, т. Е. Указатель на головной узел не является глобальным.
2) Он не должен возвращать указатель на головной узел.
3) Он не должен принимать указатель на указатель на головной узел.

Вы можете предположить, что Связанный список никогда не станет пустым.

Пусть имя функции будет deleteNode (). В простой реализации функции необходимо изменить указатель заголовка, когда удаляемый узел является первым узлом. Как обсуждалось в предыдущем посте , когда функция изменяет указатель головы, функция должна использовать один из указанных подходов , мы не можем использовать ни один из этих подходов здесь.

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

C ++

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

using namespace std;

  
/ * структура узла связанного списка * /

class Node 

{ 

    public:

    int data; 

    Node *next; 

}; 

  

void deleteNode(Node *head, Node *n) 

{ 

    // Когда удаляемый узел является головным узлом

    if(head == n) 

    { 

        if(head->next == NULL) 

        { 

            cout << "There is only one node." <<

                    " The list can't be made empty "; 

            return; 

        } 

  

        / * Копировать данные следующего узла в заголовок * /

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

  

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

        n = head->next; 

  

        // Удалить ссылку следующего узла

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

  

        // свободная память

        free(n); 

  

        return; 

    } 

  

  

    // Если не первый узел, следовать

    // нормальный процесс удаления

  

    // найти предыдущий узел

    Node *prev = head; 

    while(prev->next != NULL && prev->next != n) 

        prev = prev->next; 

  

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

    if(prev->next == NULL) 

    { 

        cout << "\nGiven node is not present in Linked List"; 

        return; 

    } 

  

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

    prev->next = prev->next->next; 

  

    // Свободная память

    free(n); 

  

    return; 

} 

  
/ * Утилита для вставки узла в начале * /

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 *head) 

{ 

    while(head!=NULL) 

    { 

        cout<<head->data<<" "; 

        head=head->next; 

    } 

    cout<<endl;

} 

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

int main() 

{ 

    Node *head = NULL; 

  

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

    12-> 15-> 10-> 11-> 5-> 6-> 2-> 3 * /

    push(&head,3); 

    push(&head,2); 

    push(&head,6); 

    push(&head,5); 

    push(&head,11); 

    push(&head,10); 

    push(&head,15); 

    push(&head,12); 

  

    cout<<"Given Linked List: "; 

    printList(head); 

  

    / * Давайте удалим узел со значением 10 * /

    cout<<"\nDeleting node "<< head->next->next->data<<" "; 

    deleteNode(head, head->next->next); 

  

    cout<<"\nModified Linked List: "; 

    printList(head); 

  

    / * Давайте удалим первый узел * /

    cout<<"\nDeleting first node "; 

    deleteNode(head, head); 

  

    cout<<"\nModified Linked List: "; 

    printList(head); 

    return 0; 

} 

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

С

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

  
/ * структура узла связанного списка * /

struct Node

{

    int data;

    struct Node *next;

};

  

void deleteNode(struct Node *head, struct Node *n)

{

    // Когда удаляемый узел является головным узлом

    if(head == n)

    {

        if(head->next == NULL)

        {

            printf("There is only one node. The list can't be made empty ");

            return;

        }

  

        / * Копировать данные следующего узла в заголовок * /

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

  

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

        n = head->next;

  

        // Удалить ссылку следующего узла

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

  

        // свободная память

        free(n);

  

        return;

    }

  

  

    // Если не первый узел, следуйте нормальному процессу удаления

  

    // найти предыдущий узел

    struct Node *prev = head;

    while(prev->next != NULL && prev->next != n)

        prev = prev->next;

  

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

    if(prev->next == NULL)

    {

        printf("\n Given node is not present in Linked List");

        return;

    }

  

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

    prev->next = prev->next->next;

  

    // Свободная память

    free(n);

  

    return; 

}

  
/ * Утилита для вставки узла в начале * /

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 *head)

{

    while(head!=NULL)

    {

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

        head=head->next;

    }

    printf("\n");

}

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

int main()

{

    struct Node *head = NULL;

  

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

      12-> 15-> 10-> 11-> 5-> 6-> 2-> 3 * /

    push(&head,3);

    push(&head,2);

    push(&head,6);

    push(&head,5);

    push(&head,11);

    push(&head,10);

    push(&head,15);

    push(&head,12);

  

    printf("Given Linked List: ");

    printList(head);

  

    / * Давайте удалим узел со значением 10 * /

    printf("\nDeleting node %d: ", head->next->next->data);

    deleteNode(head, head->next->next);

  

    printf("\nModified Linked List: ");

    printList(head);

  

    / * Давайте удалим первый узел * /

    printf("\nDeleting first node ");

    deleteNode(head, head);

  

    printf("\nModified Linked List: ");

    printList(head);

  

    getchar();

    return 0;

}

Python 3

# Класс узла

class Node:

  

    def __init__(self, data):

        self.data = data

        self.next = None

  
# LinkedList class

class LinkedList:

  

    def __init__(self):

        self.head = None

  

    def deleteNode(self, data):

        temp = self.head

  

        # если удаляемый элемент находится сверху

        if (temp.data == data):

  

            if temp.next is not None:

                temp.data = temp.next.data

                temp.next = temp.next.next

            else:

                print("\nThere is only one node. \

                         The list can't be made empty")

            return

  

        # если не наверху, то мы будем искать его один за другим.

        while (temp.next is not None and 

               temp.next.data != data):

            temp = temp.next

              

        # если temp-> next равно нулю

        # тогда элемента нет

        if temp.next is None:

            print('\n Given node is not present in Linked List')

              

        Элемент # else присутствует, и мы его удаляем

        else:

            temp.next = temp.next.next

          

    # Чтобы вставить новый элемент в связанный список

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Для печати всех элементов связанного списка

    def PrintList(self):

  

        temp = self.head

        while(temp):

            print(temp.data, end = " ")

            temp = temp.next

  
Код водителя

llist = LinkedList()

llist.push(3)

llist.push(2)

llist.push(6)

llist.push(5)

llist.push(11)

llist.push(10)

llist.push(15)

llist.push(12)

  

print("Given Linked List: ", end = ' ')

llist.PrintList()

print("\n\nDeleting node 10:")

llist.deleteNode(10)

print("Modified Linked List: ", end = ' ')

llist.PrintList()

print("\n\nDeleting first node")

llist.deleteNode(12)

print("Modified Linked List: ", end = ' ')

llist.PrintList()

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

Джава

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

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    void deleteNode(Node node, Node n) {

          

        // Когда удаляемый узел является головным узлом

        if (node == n) {

            if (node.next == null) {

                System.out.println("There is only one node. The list "

                                 + "can't be made empty ");

                return;

            }

  

            / * Копировать данные следующего узла в заголовок * /

            node.data = node.next.data;

  

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

            n = node.next;

  

            // Удалить ссылку следующего узла

            node.next = node.next.next;

  

            // свободная память

            System.gc();

  

            return;

        }

  

        // Если не первый узел, следуйте нормальному процессу удаления

        // найти предыдущий узел

        Node prev = node;

        while (prev.next != null && prev.next != n) {

            prev = prev.next;

        }

  

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

        if (prev.next == null) {

            System.out.println("Given node is not present in Linked List");

            return;

        }

  

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

        prev.next = prev.next.next;

  

        // Свободная память

        System.gc();

  

        return;

    }

  

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

    void printList(Node head) {

        while (head != null) {

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

            head = head.next;

        }

        System.out.println("");

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.head = new Node(12);

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

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

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

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

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

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

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

  

        System.out.println("Given Linked List :");

        list.printList(head);

        System.out.println("");

          

        // Давайте удалим узел со значением 10

        System.out.println("Deleting node :" + head.next.next.data);

        list.deleteNode(head, head.next.next);

  

        System.out.println("Modified Linked list :");

        list.printList(head);

        System.out.println("");

  

        // удаляем первый узел

        System.out.println("Deleting first Node");

        list.deleteNode(head, head);

        System.out.println("Modified Linked List");

        list.printList(head);

  

    }

}

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

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 deleteNode(Node node, Node n)

    {

          

        // Когда удаляемый узел является головным узлом

        if (node == n)

        {

            if (node.next == null) 

            {

                Console.WriteLine("There is only one node. The list "

                                + "can't be made empty ");

                return;

            }

  

            / * Копировать данные следующего узла в заголовок * /

            node.data = node.next.data;

  

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

            n = node.next;

  

            // Удалить ссылку следующего узла

            node.next = node.next.next;

  

            // свободная память

            GC.Collect();

  

            return;

        }

  

        // Если не первый узел, следовать

        // нормальный процесс удаления

        // найти предыдущий узел

        Node prev = node;

        while (prev.next != null && prev.next != n) 

        {

            prev = prev.next;

        }

  

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

        if (prev.next == null) 

        {

            Console.WriteLine("Given node is not" +

                               "present in Linked List");

            return;

        }

  

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

        prev.next = prev.next.next;

  

        // Свободная память

        GC.Collect();

  

        return;

    }

  

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

    void printList(Node head) 

    {

        while (head != null)

        {

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

            head = head.next;

        }

        Console.WriteLine("");

    }

  

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

    public static void Main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(12);

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

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

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

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

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

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

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

  

        Console.WriteLine("Given Linked List :");

        list.printList(list.head);

        Console.WriteLine("");

          

        // Давайте удалим узел со значением 10

        Console.WriteLine("Deleting node :" +

                            list.head.next.next.data);

        list.deleteNode(list.head, list.head.next.next);

  

        Console.WriteLine("Modified Linked list :");

        list.printList(list.head);

        Console.WriteLine("");

  

        // удаляем первый узел

        Console.WriteLine("Deleting first Node");

        list.deleteNode(list.head, list.head);

        Console.WriteLine("Modified Linked List");

        list.printList(list.head);

    }

} 

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

Выход:

Given Linked List: 12 15 10 11 5 6 2 3

Deleting node 10:
Modified Linked List: 12 15 11 5 6 2 3

Deleting first node
Modified Linked List: 15 11 5 6 2 3

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

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

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

0.00 (0%) 0 votes