Рубрики

Удалить узлы, которые имеют большее значение на правой стороне

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

Примеры:
a) Список 12-> 15-> 10-> 11-> 5-> 6-> 2-> 3-> NULL следует изменить на 15-> 11-> 6-> 3-> NULL. Обратите внимание, что 12, 10, 5 и 2 были удалены, потому что справа есть большее значение.

Когда мы исследуем 12, мы видим, что после 12 есть один узел со значением больше 12 (т.е. 15), поэтому мы удаляем 12.
Когда мы исследуем 15, мы не обнаруживаем ни одного узла после 15, который имеет значение больше 15, поэтому мы сохраняем этот узел.
Когда мы идем так, мы получаем 15-> 6-> 3

б) Список 10-> 20-> 30-> 40-> 50-> 60-> NULL должен быть изменен на 60-> NULL. Обратите внимание, что 10, 20, 30, 40 и 50 были удалены, поскольку все они имеют большее значение с правой стороны.

c) Список 60-> 50-> 40-> 30-> 20-> 10-> NULL не должен изменяться.

Способ 1 (простой)
Используйте две петли. Во внешнем цикле выбирайте узлы связанного списка по одному. Во внутреннем цикле проверьте, существует ли узел, значение которого больше выбранного узла. Если существует узел, значение которого больше, удалите выбранный узел.
Сложность времени: O (n ^ 2)

Метод 2 (Используйте Обратный)
Спасибо Paras за предоставленный ниже алгоритм.
1. Переверните список.
2. Пройдите обратный список. Держи максимум до сих пор. Если следующий узел меньше, чем max, удалите следующий узел, в противном случае max = следующий узел.
3. Снова переверните список, чтобы сохранить исходный порядок.

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

Спасибо R.Srinivasan за предоставленный ниже код.

С

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

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

struct Node {

    int data;

    struct Node* next;

};

  
/ * прототип для служебных функций * /

void reverseList(struct Node** headref);

void _delLesserNodes(struct Node* head);

  
/ * Удаляет узлы, у которых есть узел с большим значением узла

  на левой стороне * /

void delLesserNodes(struct Node** head_ref)

{

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

    reverseList(head_ref);

  

    / * 2) В обратном списке удалите узлы, у которых есть узел

       с большим значением узла на левой стороне. Обратите внимание, что голова

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

    _delLesserNodes(*head_ref);

  

    / * 3) Снова переверните связанный список, чтобы сохранить

       оригинальный заказ * /

    reverseList(head_ref);

}

  
/ * Удаляет узлы, которые имеют большее значение узла (ов) на левой стороне * /

void _delLesserNodes(struct Node* head)

{

    struct Node* current = head;

  

    / * Инициализировать макс. * /

    struct Node* maxnode = head;

    struct Node* temp;

  

    while (current != NULL && current->next != NULL) {

        / * Если ток меньше максимального, удалить ток * /

        if (current->next->data < maxnode->data) {

            temp = current->next;

            current->next = temp->next;

            free(temp);

        }

  

        / * Если ток больше, чем max, обновите max и

            переместить ток * /

        else {

            current = current->next;

            maxnode = current;

        }

    }

}

  
/ * Служебная функция для вставки узла в начале * /

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 reverseList(struct Node** headref)

{

    struct Node* current = *headref;

    struct Node* prev = NULL;

    struct Node* next;

    while (current != NULL) {

        next = current->next;

        current->next = prev;

        prev = current;

        current = next;

    }

    *headref = prev;

}

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

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 \n");

    printList(head);

  

    delLesserNodes(&head);

  

    printf("Modified Linked List \n");

    printList(head);

  

    return 0;

}

Джава

// Java-программа для удаления узлов, которые имеют большее значение
// правая сторона

class LinkedList {

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

  

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

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Удаляет узлы, у которых есть узел с большим

       значение узла на левой стороне * /

    void delLesserNodes()

    {

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

        reverseList();

  

        / * 2) В обратном списке удалите узлы, которые

           иметь узел с большим значением узла слева

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

           потому что это самый левый узел. * /

        _delLesserNodes();

  

        / * 3) Снова перевернуть связанный список, чтобы сохранить

           оригинальный заказ * /

        reverseList();

    }

  

    / * Удаляет узлы, которые имеют большее значение узла (ов)

       на левой стороне * /

    void _delLesserNodes()

    {

        Node current = head;

  

        / * Инициализация макс. * /

        Node maxnode = head;

        Node temp;

  

        while (current != null && current.next != null) {

            / * Если ток меньше максимального, то удалить

               текущий */

            if (current.next.data < maxnode.data) {

                temp = current.next;

                current.next = temp.next;

                temp = null;

            }

  

            / * Если ток больше максимального, тогда обновить

               макс и ток перемещения * /

            else {

                current = current.next;

                maxnode = current;

            }

        }

    }

  

    / * Сервисные функции * /

  

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

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

    / * Функция перевернуть связанный список * /

    void reverseList()

    {

        Node current = head;

        Node prev = null;

        Node next;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

        }

        head = prev;

    }

  

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

    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();

  

        / * Построен связанный список 12-> 15-> 10-> 11->

           5-> 6-> 2-> 3 * /

        llist.push(3);

        llist.push(2);

        llist.push(6);

        llist.push(5);

        llist.push(11);

        llist.push(10);

        llist.push(15);

        llist.push(12);

  

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

        llist.printList();

  

        llist.delLesserNodes();

  

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

        llist.printList();

    }

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

Выход:

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

Источник:
http://espressocode.top/forum/topic/amazon-interview-question-for-software-engineerdeveloper-about-linked-lists-6

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

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

Удалить узлы, которые имеют большее значение на правой стороне

0.00 (0%) 0 votes