Рубрики

Направить указатель на максимальное значение правого узла в связанном списке

Данный односвязный список с каждым узлом, имеющим дополнительный «произвольный» указатель, который в данный момент указывает на NULL. Нам нужно сделать «произвольный» указатель на узел наибольшего значения в связанном списке с правой стороны.

Простое решение — обойти все узлы один за другим. Для каждого узла найдите узел с наибольшим значением справа и измените следующий указатель. Сложность времени этого решения O (n 2 ).

Эффективное решение может работать за O (n) времени. Ниже приведены шаги.

  1. Обратный заданный связанный список.
  2. Начните обход связанного списка и сохраните узел максимального значения, встреченный до сих пор. Сделайте арбитр каждого узла, чтобы он указывал на макс. Если данные в текущем узле пока больше, чем max, обновите max.
  3. Отменить измененный связанный список и вернуть голову.

Ниже приведена реализация вышеуказанных шагов.

C ++

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

using namespace std;

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

struct Node

{

    int data;

    Node* next, *arbit;

};

  
/ * Функция перевернуть связанный список * /
Node* reverse(Node *head)
{

    Node *prev = NULL, *current = head, *next;

    while (current != NULL)

    {

        next  = current->next;

        current->next = prev;

        prev = current;

        current = next;

    }

    return prev;

}

  
// Эта функция заполняет произвольный указатель в каждом
// узел с наибольшим значением справа от него.
Node* populateArbit(Node *head)
{

    // Обратный заданный связанный список

    head = reverse(head);

  

    // Инициализируем указатель на узел максимального значения

    Node *max = head;

  

    // Обход перевернутого списка

    Node *temp = head->next;

    while (temp != NULL)

    {

        // Подключаем макс через арбитр

        temp->arbit = max;

  

        // Обновить макс при необходимости

        if (max->data < temp->data)

            max = temp;

  

        // Продвигаться в обратном списке

        temp = temp->next;

    }

  

    // Отменить измененный связанный список и вернуть

    // голова.

    return reverse(head);

}

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

void printNextArbitPointers(Node *node)

{

    printf("Node\tNext Pointer\tArbit Pointer\n");

    while (node!=NULL)

    {

        cout << node->data << "\t\t";

  

        if (node->next)

            cout << node->next->data << "\t\t";

        else cout << "NULL" << "\t\t";

  

        if (node->arbit)

            cout << node->arbit->data;

        else cout << "NULL";

  

        cout << endl;

        node = node->next;

    }

}

  
/ * Функция для создания нового узла с заданными данными * /

Node *newNode(int data)

{

    Node *new_node = new Node;

    new_node->data = data;

    new_node->next = NULL;

    return new_node;

}

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

int main()

{

    Node *head = newNode(5);

    head->next = newNode(10);

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

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

  

    head = populateArbit(head);

  

    printf("Resultant Linked List is: \n");

    printNextArbitPointers(head);

  

    return 0;

}

Джава

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

class GfG 

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

static class Node 

    int data; 

    Node next, arbit; 

}

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

static Node reverse(Node head) 

    Node prev = null, current = head, next = null

    while (current != null

    

        next = current.next; 

        current.next = prev; 

        prev = current; 

        current = next; 

    

    return prev; 

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

static Node populateArbit(Node head) 

    // Обратный заданный связанный список

    head = reverse(head); 

  

    // Инициализируем указатель на узел максимального значения

    Node max = head; 

  

    // Обход перевернутого списка

    Node temp = head.next; 

    while (temp != null

    

        // Подключаем макс через арбитр

        temp.arbit = max; 

  

        // Обновить макс при необходимости

        if (max.data < temp.data) 

            max = temp; 

  

        // Продвигаться в обратном списке

        temp = temp.next; 

    

  

    // Отменить измененный связанный список и вернуть

    // голова.

    return reverse(head); 

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

static void printNextArbitPointers(Node node) 

    System.out.println("Node\tNext Pointer\tArbit Pointer"); 

    while (node != null

    

        System.out.print(node.data + "\t\t"); 

  

        if (node.next != null

            System.out.print(node.next.data + "\t\t"); 

        else

            System.out.print("NULL" +"\t\t"); 

  

        if (node.arbit != null

            System.out.print(node.arbit.data); 

        else

            System.out.print("NULL"); 

  

        System.out.println(); 

        node = node.next; 

    

  
/ * Функция для создания нового узла с заданными данными * /

static Node newNode(int data) 

    Node new_node = new Node(); 

    new_node.data = data; 

    new_node.next = null

    return new_node; 

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

public static void main(String[] args) 

    Node head = newNode(5); 

    head.next = newNode(10); 

    head.next.next = newNode(2); 

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

  

    head = populateArbit(head); 

  

    System.out.println("Resultant Linked List is: "); 

    printNextArbitPointers(head); 

  
}

  
// Этот код предоставлен Prerna Saini.

C #

// C # программа для указания указателей на арбитры
// к верхнему значению справа

using System;

  

class GfG 

  

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

    class Node 

    

        public int data; 

        public Node next, arbit; 

    }

  

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

    static Node reverse(Node head) 

    

        Node prev = null, current = head, next = null

        while (current != null

        

            next = current.next; 

            current.next = prev; 

            prev = current; 

            current = next; 

        

        return prev; 

    

  

    // Эта функция заполняет произвольный указатель в каждом

    // узел с наибольшим значением справа от него.

    static Node populateArbit(Node head) 

    

        // Обратный заданный связанный список

        head = reverse(head); 

  

        // Инициализируем указатель на узел максимального значения

        Node max = head; 

  

        // Обход перевернутого списка

        Node temp = head.next; 

        while (temp != null

        

            // Подключаем макс через арбитр

            temp.arbit = max; 

  

            // Обновить макс при необходимости

            if (max.data < temp.data) 

                max = temp; 

  

            // Продвигаться в обратном списке

            temp = temp.next; 

        

  

        // Обратно модифицированный связанный список

        // и вернуть голову.

        return reverse(head); 

    

  

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

    static void printNextArbitPointers(Node node) 

    

        Console.WriteLine("Node\tNext Pointer\tArbit Pointer"); 

        while (node != null

        

            Console.Write(node.data + "\t\t"); 

  

            if (node.next != null

                Console.Write(node.next.data + "\t\t"); 

            else

                Console.Write("NULL" +"\t\t"); 

  

            if (node.arbit != null

                Console.Write(node.arbit.data); 

            else

                Console.Write("NULL"); 

  

            Console.WriteLine(); 

            node = node.next; 

        

    

  

    / * Функция для создания нового узла с заданными данными * /

    static Node newNode(int data) 

    

        Node new_node = new Node(); 

        new_node.data = data; 

        new_node.next = null

        return new_node; 

    

  

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

    public static void Main(String[] args) 

    

        Node head = newNode(5); 

        head.next = newNode(10); 

        head.next.next = newNode(2); 

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

  

        head = populateArbit(head); 

  

        Console.WriteLine("Resultant Linked List is: "); 

        printNextArbitPointers(head); 

    }

}

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


Выход:

Resultant Linked List is: 
Node    Next Pointer    Arbit Pointer
5               10              10
10              2               3
2               3               3
3               NULL            NULL

Рекурсивное решение:
Мы можем рекурсивно добраться до последнего узла и пройти по связанному списку с конца. Рекурсивное решение не требует обращения к связанному списку. Мы также можем использовать стек вместо рекурсии для временного хранения узлов. Спасибо Santosh Kumar Mishra за предоставление этого решения.

C ++

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

using namespace std;

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

struct Node

{

    int data;

    Node* next, *arbit;

};

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

void populateArbit(Node *head)

{

    // использование статического maxNode для отслеживания максимума

    // адрес узла орбиты справа

    static Node *maxNode;

  

    // если голова пуста, просто вернуть список

    if (head == NULL)

        return;

  

    / * если head-> next равно нулю, это означает, что мы достигли

       последний узел просто обновляет max и maxNode * /

    if (head->next == NULL)

    {

        maxNode = head;

        return;

    }

  

    / * Вызов populateArbit к следующему узлу * /

    populateArbit(head->next);

  

    / * обновление арбитражного узла текущего

     узел с максимальным значением на правой стороне * /

    head->arbit = maxNode;

  

    / * если идентификатор текущего значения узла больше, чем

     предыдущий правый узел затем обновите его * /

    if (head->data > maxNode->data)

        maxNode = head;

  

   return;

}

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

void printNextArbitPointers(Node *node)

{

    printf("Node\tNext Pointer\tArbit Pointer\n");

    while (node!=NULL)

    {

        cout << node->data << "\t\t";

  

        if(node->next)

            cout << node->next->data << "\t\t";

        else cout << "NULL" << "\t\t";

  

        if(node->arbit)

            cout << node->arbit->data;

        else cout << "NULL";

  

        cout << endl;

        node = node->next;

    }

}

  
/ * Функция для создания нового узла с заданными данными * /

Node *newNode(int data)

{

    Node *new_node = new Node;

    new_node->data = data;

    new_node->next = NULL;

    return new_node;

}

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

int main()

{

    Node *head = newNode(5);

    head->next = newNode(10);

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

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

  

    populateArbit(head);

  

    printf("Resultant Linked List is: \n");

    printNextArbitPointers(head);

  

    return 0;

}

Джава

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

class GfG

{

  

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

    static class Node

    {

        int data;

        Node next, arbit;

    }

  

    static Node maxNode;

  

    // Эта функция заполняет произвольный указатель в каждом

    // узел с наибольшим значением справа от него.

    static void populateArbit(Node head)

    {

  

        // если голова пуста, просто вернуть список

        if (head == null)

            return;

  

        / * если head-> next равно нулю, это означает, что мы достигли

        последний узел просто обновляет max и maxNode * /

        if (head.next == null)

        {

            maxNode = head;

            return;

        }

  

        / * Вызов populateArbit к следующему узлу * /

        populateArbit(head.next);

  

        / * обновление арбитражного узла текущего

        узел с максимальным значением на правой стороне * /

        head.arbit = maxNode;

  

        / * если идентификатор текущего значения узла больше, чем

        предыдущий правый узел затем обновите его * /

        if (head.data > maxNode.data)

            maxNode = head;

  

        return;

    }

  

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

    static void printNextArbitPointers(Node node)

    {

        System.out.println("Node\tNext Pointer\tArbit Pointer");

        while (node != null)

        {

            System.out.print(node.data + "\t\t\t");

  

            if (node.next != null)

                System.out.print(node.next.data + "\t\t\t\t");

            else

                System.out.print("NULL" +"\t\t\t");

  

            if (node.arbit != null)

                System.out.print(node.arbit.data);

            else

                System.out.print("NULL");

  

            System.out.println();

            node = node.next;

        }

    }

  

    / * Функция для создания нового узла с заданными данными * /

    static Node newNode(int data)

    {

        Node new_node = new Node();

        new_node.data = data;

        new_node.next = null;

        return new_node;

    }

  

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

    public static void main(String[] args)

    {

        Node head = newNode(5);

        head.next = newNode(10);

        head.next.next = newNode(2);

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

  

        populateArbit(head);

  

        System.out.println("Resultant Linked List is: ");

        printNextArbitPointers(head);

  

    }

}

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

C #

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

using System;

      

class GfG

{

  

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

    public class Node

    {

        public int data;

        public Node next, arbit;

    }

  

    static Node maxNode;

  

    // Эта функция заполняет произвольный указатель в каждом

    // узел с наибольшим значением справа от него.

    static void populateArbit(Node head)

    {

  

        // если голова пуста, просто вернуть список

        if (head == null)

            return;

  

        / * если head-> next равно нулю, это означает, что мы достигли

        последний узел просто обновляет max и maxNode * /

        if (head.next == null)

        {

            maxNode = head;

            return;

        }

  

        / * Вызов populateArbit к следующему узлу * /

        populateArbit(head.next);

  

        / * обновление арбитражного узла текущего

        узел с максимальным значением на правой стороне * /

        head.arbit = maxNode;

  

        / * если идентификатор текущего значения узла больше, чем

        предыдущий правый узел затем обновите его * /

        if (head.data > maxNode.data)

            maxNode = head;

  

        return;

    }

  

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

    static void printNextArbitPointers(Node node)

    {

        Console.WriteLine("Node\tNext Pointer\tArbit Pointer");

        while (node != null)

        {

            Console.Write(node.data + "\t\t\t");

  

            if (node.next != null)

                Console.Write(node.next.data + "\t\t\t\t");

            else

                Console.Write("NULL" +"\t\t\t");

  

            if (node.arbit != null)

                Console.Write(node.arbit.data);

            else

                Console.Write("NULL");

  

            Console.WriteLine();

            node = node.next;

        }

    }

  

    / * Функция для создания нового узла с заданными данными * /

    static Node newNode(int data)

    {

        Node new_node = new Node();

        new_node.data = data;

        new_node.next = null;

        return new_node;

    }

  

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

    public static void Main(String[] args)

    {

        Node head = newNode(5);

        head.next = newNode(10);

        head.next.next = newNode(2);

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

  

        populateArbit(head);

  

        Console.WriteLine("Resultant Linked List is: ");

        printNextArbitPointers(head);

  

    }

}

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

Выход:

Resultant Linked List is: 
Node    Next Pointer    Arbit Pointer
5               10              10
10              2               3
2               3               3
3               NULL            NULL

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

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

Направить указатель на максимальное значение правого узла в связанном списке

0.00 (0%) 0 votes