Рубрики

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

Имея указатель на удаляемый узел, удалите узел. Обратите внимание, что у нас нет указателя на головной узел.

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

Быстрое решение состоит в том, чтобы скопировать данные из следующего узла в удаляемый узел и удалить следующий узел. Что-то вроде следующего.

    // Find next node using next pointer
    struct Node *temp  = node_ptr->next;

    // Copy data of next node to this node
    node_ptr->data  = temp->data;

    // Unlink next node
    node_ptr->next  = temp->next;

    // Delete next node
    free(temp);

Программа:

C ++

#include <bits/stdc++.h>

using namespace std;

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

class Node {

public:

    int data;

    Node* next;

};

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

    списка и int, нажмите новый узел на передней панели

    из списка. * /

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)

{

    Node* temp = head;

    while (temp != NULL) {

        cout << temp->data << " ";

        temp = temp->next;

    }

}

  

void deleteNode(Node* node)

{

    Node* prev;

    if (node == NULL)

        return;

    else {

        while (node->next != NULL) {

            node->data = node->next->data;

            prev = node;

            node = node->next;

        }

        prev->next = NULL;

    }

}

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

int main()

{

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

    Node* head = NULL;

  

    / * Используйте push () для построения списка ниже

    1-> 12-> 1-> 4-> 1 * /

    push(&head, 1);

    push(&head, 4);

    push(&head, 1);

    push(&head, 12);

    push(&head, 1);

  

    cout << "Before deleting \n";

    printList(head);

  

    / * Я удаляю саму голову.

        Вы можете проверить больше случаев * /

    deleteNode(head);

  

    cout << "\nAfter deleting \n";

    printList(head);

    return 0;

}

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

С

#include <assert.h>
#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 printList(struct Node* head)

{

    struct Node* temp = head;

    while (temp != NULL) {

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

        temp = temp->next;

    }

}

  

void deleteNode(struct Node* node)

{

    struct Node* prev;

    if (node == NULL)

        return;

    else {

        while (node->next != NULL) {

            node->data = node->next->data;

            prev = node;

            node = node->next;

        }

        prev->next = NULL;

    }

}

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

int main()

{

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

    struct Node* head = NULL;

  

    / * Используйте push () для построения списка ниже

    1-> 12-> 1-> 4-> 1 * /

    push(&head, 1);

    push(&head, 4);

    push(&head, 1);

    push(&head, 12);

    push(&head, 1);

  

    printf("Before deleting \n");

    printList(head);

  

    / * Я удаляю саму голову.

        Вы можете проверить больше случаев * /

    deleteNode(head);

  

    printf("\nAfter deleting \n");

    printList(head);

    getchar();

    return 0;

}

Джава

class LinkedList {

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

  

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Учитывая ссылку на заголовок списка и int,

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

    public void push(int new_data)

    {

        / * 1. выделить узел и поместить данные * /

        Node new_Node = new Node(new_data);

  

        / * 2. Сделать следующий новый узел в качестве головы * /

        new_Node.next = head;

  

        / * 3. Переместить голову, чтобы указать на новый узел * /

        head = new_Node;

    }

  

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

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

    public void printList()

    {

        Node tNode = head;

        while (tNode != null) {

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

            tNode = tNode.next;

        }

    }

  

    public void deleteNode(Node Node_ptr)

    {

        Node temp = Node_ptr.next;

        Node_ptr.data = temp.data;

        Node_ptr.next = temp.next;

        temp = null;

    }

  

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

  

        / * Используйте push () для построения списка ниже

        1-> 12-> 1-> 4-> 1 * /

        llist.push(1);

        llist.push(4);

        llist.push(1);

        llist.push(12);

        llist.push(1);

  

        System.out.println("Before deleting");

        llist.printList();

  

        / * Я удаляю саму голову.

        Вы можете проверить больше случаев * /

        llist.deleteNode(llist.head);

  

        System.out.println("\nAfter Deleting");

        llist.printList();

    }

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

питон

# класс для определения узла с
# данные и следующий указатель

class Node():

  

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

    def __init__(self, val = None):

        self.data = val

        self.next = None

  
# подтолкнуть узел в начало списка

def push(head, val):

  

    # выделить новый узел

    newnode = Node(val)

  

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

    newnode.next = head.next

  

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

    head.next = newnode

  
# функция для печати списка

def print_list(head):

  

    temp = head.next

    while(temp != None):

        print(temp.data, end = ' ')

        temp = temp.next

    print()

  
# функция для удаления узла
# основная логика в этом

def delete_node(node):

  

    prev = Node()

  

    if(node == None):

        return

    else:

        while(node.next != None):

            node.data = node.next.data

            prev = node

            node = node.next

  

        prev.next = None

  

  

if __name__ == '__main__':

  

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

    # это узел, который просто указывает на

    # первый узел в списке

    head = Node()

  

    # построить приведенный ниже список

    # 1-> 12-> 1-> 4-> 1

    push(head, 1)

    push(head, 4)

    push(head, 1)

    push(head, 12)

    push(head, 1)

  

    print('list before deleting:')

    print_list(head)

  

    # удаление первого узла в списке

    delete_node(head.next)

  

    print('list after deleting: ')

    print_list(head)

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

C #

using System;

      

public class LinkedList 

{

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

  

    public class Node

    {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Учитывая ссылку на заголовок списка и int,

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

    public void push(int new_data)

    {

        / * 1. выделить узел и поместить данные * /

        Node new_Node = new Node(new_data);

  

        / * 2. Сделать следующий новый узел в качестве головы * /

        new_Node.next = head;

  

        / * 3. Переместить голову, чтобы указать на новый узел * /

        head = new_Node;

    }

  

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

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

    public void printList()

    {

        Node tNode = head;

        while (tNode != null

        {

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

            tNode = tNode.next;

        }

    }

  

    public void deleteNode(Node Node_ptr)

    {

        Node temp = Node_ptr.next;

        Node_ptr.data = temp.data;

        Node_ptr.next = temp.next;

        temp = null;

    }

  

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

    public static void Main(String[] args)

    {

        LinkedList llist = new LinkedList();

  

        / * Используйте push () для построения списка ниже

        1-> 12-> 1-> 4-> 1 * /

        llist.push(1);

        llist.push(4);

        llist.push(1);

        llist.push(12);

        llist.push(1);

  

        Console.WriteLine("Before deleting");

        llist.printList();

  

        / * Я удаляю саму голову.

        Вы можете проверить больше случаев * /

        llist.deleteNode(llist.head);

  

        Console.WriteLine("\nAfter Deleting");

        llist.printList();

    }

}

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

Выход:

Before deleting 
1 12 1 4 1 
After deleting 
12 1 4 1 

Это решение не работает, если удаляемый узел является последним узлом списка. Чтобы заставить это решение работать, мы можем отметить конечный узел как фиктивный узел. Но программы / функции, которые используют эту функцию, также должны быть изменены.

Упражнение: попробуйте эту задачу для двусвязного списка.

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

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

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

0.00 (0%) 0 votes