Рубрики

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

Имея односвязный список, начиная со второго узла удалите все его альтернативные узлы. Например, если заданный связанный список 1-> 2-> 3-> 4-> 5, ваша функция должна преобразовать его в 1-> 3-> 5, и если данный связанный список равен 1-> 2-> 3-> 4, затем преобразовать его в 1-> 3.

Метод 1 (итеративный)
Следите за предыдущим удаляемого узла. Сначала измените следующую ссылку предыдущего узла, а затем освободите память, выделенную для узла.

C ++

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

using namespace std;

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

class Node 

    public:

    int data; 

    Node *next; 

}; 

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

void deleteAlt(Node *head) 

    if (head == NULL) 

        return

  

    / * Инициализировать предыдущий и удаляемый узел * /

    Node *prev = head; 

    Node *node = head->next; 

  

    while (prev != NULL && node != NULL) 

    

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

        prev->next = node->next; 

  

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

        free(node); 

  

        / * Обновление prev и node * /

        prev = prev->next; 

        if (prev != NULL) 

            node = prev->next; 

    

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ fun1 () и fun2 () * /
/ * Дана ссылка (указатель на указатель) на голову
списка и 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 *node) 

    while (node != NULL) 

    

        cout<< node->data<<" "

        node = node->next; 

    

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

int main() 

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

    Node* head = NULL; 

  

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

    1-> 2-> 3-> 4-> 5 * /

    push(&head, 5); 

    push(&head, 4); 

    push(&head, 3); 

    push(&head, 2); 

    push(&head, 1); 

  

    cout<<"List before calling deleteAlt() \n"

    printList(head); 

  

    deleteAlt(head); 

  

    cout<<"\nList after calling deleteAlt() \n"

    printList(head); 

  

    return 0; 

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

С

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

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

struct Node

{

    int data;

    struct Node *next;

};

  
/ * удаляет альтернативные узлы списка, начиная с заголовка * /

void deleteAlt(struct Node *head)

{

    if (head == NULL)

        return;

  

    / * Инициализировать предыдущий и удаляемый узел * /

    struct Node *prev = head;

    struct Node *node = head->next;

  

    while (prev != NULL && node != NULL)

    {

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

        prev->next = node->next;

  

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

        free(node);

  

        / * Обновление prev и node * /

        prev = prev->next;

        if (prev != NULL)

            node = prev->next;

    }

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ fun1 () и fun2 () * /
/ * Дана ссылка (указатель на указатель) на голову

  списка и 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 *node)

{

    while (node != NULL)

    {

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

        node = node->next;

    }

}

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

int main()

{

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

    struct Node* head = NULL;

  

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

      1-> 2-> 3-> 4-> 5 * /

    push(&head, 5);

    push(&head, 4);

    push(&head, 3);

    push(&head, 2);

    push(&head, 1);

  

    printf("\nList before calling deleteAlt() \n");

    printList(head);

  

    deleteAlt(head);

  

    printf("\nList after calling deleteAlt() \n");

    printList(head);

  

    return 0;

}

Джава

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

class LinkedList

{

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

   

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

    class Node

    {

        int data;

        Node next;

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

    }

  

    void deleteAlt()

    {

       if (head == null

          return;

  

       Node prev = head;

       Node now = head.next;

  

       while (prev != null && now != null

       {           

           / * Изменить следующую ссылку на прежний узел * /

           prev.next = now.next;

  

           / * Свободный узел * /

           now = null;

  

           / * Обновление предыдущая и сейчас * /

           prev = prev.next;

           if (prev != null

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

          

        / * Построенный связанный список 1-> 2-> 3-> 4-> 5-> null * /

        llist.push(5);

        llist.push(4);

        llist.push(3);

        llist.push(2);

        llist.push(1);

          

        System.out.println("Linked List before calling deleteAlt() ");

        llist.printList();

          

        llist.deleteAlt();

          

        System.out.println("Linked List after calling deleteAlt() ");

        llist.printList();

    }


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

python3

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

import math 

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

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.next = None

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

def deleteAlt(head): 

    if (head == None):

        return

  

    # Инициализировать предыдущий и удаляемый узел

    prev = head 

    now = head.next

  

    while (prev != None and now != None): 

          

        # Изменить следующую ссылку предыдущего узла

        prev.next = now.next

  

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

        now = None

  

        # Обновление prev и node

        prev = prev.next

        if (prev != None): 

            now = prev.next

      
# ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ fun1 () и fun2 ()
# Дана ссылка (пиро в пире) на голову
# списка и, нажмите новый узел на передней панели
№ списка.

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 prList(node): 

    while (node != None): 

        print(node.data, end = " "

        node = node.next

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

if __name__=='__main__'

      

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

    head = None

  

    # Использование head = push () для построения списка ниже

    # 1.2.3.4.5

    head = push(head, 5

    head = push(head, 4

    head = push(head, 3

    head = push(head, 2

    head = push(head, 1

  

    print("List before calling deleteAlt() ")

    prList(head) 

  

    deleteAlt(head) 

  

    print("\nList after calling deleteAlt() "

    prList(head) 

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

C #

// 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

              

        }

    }

  

    void deleteAlt()

    {

        if (head == null

            return;

  

        Node prev = head;

        Node now = head.next;

  

        while (prev != null && now != null

        {         

            / * Изменить следующую ссылку на прежний узел * /

            prev.next = now.next;

  

            / * Свободный узел * /

            now = null;

  

            / * Обновление предыдущая и сейчас * /

            prev = prev.next;

            if (prev != null

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

          

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

        1-> 2-> 3-> 4-> 5-> ноль * /

        llist.push(5);

        llist.push(4);

        llist.push(3);

        llist.push(2);

        llist.push(1);

          

        Console.WriteLine("Linked List before"

                            "calling deleteAlt() ");

        llist.printList();

          

        llist.deleteAlt();

          

        Console.WriteLine("Linked List after"

                            "calling deleteAlt() ");

        llist.printList();

    }

}

  
// Этот код был добавлен
// от 29AjayKumar


Выход:

List before calling deleteAlt() 
1 2 3 4 5 
List after calling deleteAlt() 
1 3 5 

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

Метод 2 (рекурсивный)
В рекурсивном коде используется тот же подход, что и в методе 1. Рекурсивный код является простым и коротким, но вызывает O (n) вызовов рекурсивных функций для связанного списка размером n.

C ++

/ * удаляет альтернативные узлы списка, начиная с заголовка * /

void deleteAlt(Node *head) 

    if (head == NULL) 

        return

  

    Node *node = head->next; 

  

    if (node == NULL) 

        return

  

    / * Изменить следующую ссылку головы * /

    head->next = node->next; 

  

    / * свободная память, выделенная для узла * /

    free(node); 

  

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

    deleteAlt(head->next); 

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

С

/ * удаляет альтернативные узлы списка, начиная с заголовка * /

void deleteAlt(struct Node *head)

{

    if (head == NULL)

        return;

  

    struct Node *node = head->next;

  

    if (node == NULL)

        return;

  

    / * Изменить следующую ссылку головы * /

    head->next = node->next;

  

    / * свободная память, выделенная для узла * /

    free(node);

  

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

    deleteAlt(head->next);

}

Джава

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

static Node deleteAlt(Node head) 

    if (head == null

        return

  

    Node node = head.next; 

  

    if (node == null

        return

  

    / * Изменить следующую ссылку головы * /

    head.next = node.next; 

  

  

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

    head.next = deleteAlt(head.next); 

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

python3

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

def deleteAlt(head): 

    if (head == None): 

        return

  

    node = head.next

  

    if (node == None): 

        return

  

    # Изменить следующую ссылку головы

    head.next = node.next

  

    # свободная память, выделенная для узла

    #free (узел)

  

    # Рекурсивно вызывать нового следующего руководителя

    deleteAlt(head.next

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

C #

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

static Node deleteAlt(Node head) 

    if (head == null

        return

  

    Node node = head.next; 

  

    if (node == null

        return

  

    / * Изменить следующую ссылку головы * /

    head.next = node.next; 

  

  

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

    head.next = deleteAlt(head.next); 

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


Сложность времени: O (n)

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

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

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

0.00 (0%) 0 votes