Рубрики

Клонировать связанный список со следующим и случайным указателем | Набор 2

Мы уже обсудили 2 разных способа клонирования связанного списка. В этом посте обсуждается еще один простой способ клонирования связанного списка.

Идея заключается в использовании хеширования. Ниже приведен алгоритм.
1. Просмотрите исходный связанный список и сделайте копию с точки зрения данных.
2. Создайте хэш-карту пары ключ-значение с исходным узлом связанного списка и скопированным узлом связанного списка.
3. Снова просмотрите исходный связанный список и, используя хэш-карту, настройте следующую и случайную ссылку на клонированные узлы связанного списка.

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

C ++

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

using namespace std;

  

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

class Node

{

    public:

    int data;// Данные узла

      

    // Следующая и случайная ссылка

    Node *next, *random;

  

    Node(int data)

    {

        this->data = data;

        this->next = this->random = NULL;

    }

};

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

class LinkedList

{

    public:

    Node *head;// Ссылка на заголовок связанного списка

  

    LinkedList(Node *head)

    {

        this->head = head;

    }

  

    // метод push для размещения данных всегда

    // голова в связанном списке.

    void push(int data)

    {

        Node *node = new Node(data);

        node->next = head;

        head = node;

    }

  

    // Метод для печати списка.

    void print()

    {

        Node *temp = head;

        while (temp != NULL)

        {

            Node *random = temp->random;

            int randomData = (random != NULL)?

                         random->data: -1;

            cout << "Data = " << temp->data 

                 << ", ";

            cout << "Random Data = " << 

                 randomData << endl;

            temp = temp->next;

        }

        cout << endl;

    }

  

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

    // главная ссылка клонированной ссылки

    // список.

    LinkedList* clone()

    {

        // Инициализируем две ссылки,

        // один с оригинальной головой списка.

        Node *origCurr = head;

        Node *cloneCurr = NULL;

  

        // Хеш-карта, которая содержит узел

        // для отображения узла оригинала

        // и клонированный связанный список.

        unordered_map<Node*, Node*> mymap;

  

        // Пройдемся по оригинальному списку и

        // сделать копию этого в

        // клонировать связанный список.

        while (origCurr != NULL)

        {

            cloneCurr = new Node(origCurr->data);

            mymap[origCurr] = cloneCurr;

            origCurr = origCurr->next;

        }

  

        // Корректировка исходного списка

        // снова ссылка

        origCurr = head;

  

        // Обход исходного списка снова

        // настроить следующий и случайный

        // ссылки на список клонов, использующие

        // карта хешей.

        while (origCurr != NULL)

        {

            cloneCurr = mymap[origCurr];

            cloneCurr->next = mymap[origCurr->next];

            cloneCurr->random = mymap[origCurr->random];

            origCurr = origCurr->next;

        }

  

        // возвращаем ссылку на голову

        // список клонов.

        return new LinkedList(mymap[head]);

    }

};

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

int main()

{

    // Подталкиваем данные в связанном списке.

    LinkedList *mylist = new LinkedList(new Node(5));

    mylist->push(4);

    mylist->push(3);

    mylist->push(2);

    mylist->push(1);

  

    // Настройка случайных ссылок.

    mylist->head->random = mylist->head->next->next;

  

    mylist->head->next->random =

        mylist->head->next->next->next;

  

    mylist->head->next->next->random =

        mylist->head->next->next->next->next;

  

    mylist->head->next->next->next->random =

        mylist->head->next->next->next->next->next;

  

    mylist->head->next->next->next->next->random =

        mylist->head->next;

  

    // Делаем клон оригинала

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

    LinkedList *clone = mylist->clone();

  

    // Распечатать оригинал и клонировать

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

    cout << "Original linked list\n";

    mylist->print();

    cout << "\nCloned linked list\n";

    clone->print();

}
// Этот код предоставлен Чхави

Джава

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

import java.util.HashMap;

import java.util.Map;

  
// Класс узла связанного списка

class Node

{

    int data;// Данные узла

    Node next, random;// Следующая и случайная ссылка

  

    // Узел конструктор

    public Node(int data)

    {

        this.data = data;

        this.next = this.random = null;

    }

}

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

class LinkedList

{

    Node head;// Ссылка на заголовок связанного списка

  

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

    public LinkedList(Node head)

    {

        this.head = head;

    }

  

    // метод push, чтобы данные всегда были во главе

    // в связанном списке.

    public void push(int data)

    {

        Node node = new Node(data);

        node.next = this.head;

        this.head = node;

    }

  

    // Метод для печати списка.

    void print()

    {

        Node temp = head;

        while (temp != null)

        {

            Node random = temp.random;

            int randomData = (random != null)? random.data: -1;

            System.out.println("Data = " + temp.data +

                               ", Random data = "+ randomData);

            temp = temp.next;

        }

    }

  

    // Актуальный метод клонирования, который возвращает голову

    // ссылка на клонированный связанный список.

    public LinkedList clone()

    {

        // Инициализируем две ссылки, одну с оригиналом

        // список головы.

        Node origCurr = this.head, cloneCurr = null;

  

        // Хеш-карта, которая содержит отображение узла на узел

        // оригинальный и клонированный связанный список.

        Map<Node, Node> map = new HashMap<Node, Node>();

  

        // Пройдемся по оригинальному списку и сделаем копию этого

        // в списке клонов.

        while (origCurr != null)

        {

            cloneCurr = new Node(origCurr.data);

            map.put(origCurr, cloneCurr);

            origCurr = origCurr.next;

        }

  

        // Снова корректируем исходную ссылку на список.

        origCurr = this.head;

  

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

        // и случайные ссылки на список клонов с использованием хэш-карты.

        while (origCurr != null)

        {

            cloneCurr = map.get(origCurr);

            cloneCurr.next = map.get(origCurr.next);

            cloneCurr.random = map.get(origCurr.random);

            origCurr = origCurr.next;

        }

  

        // возвращаем ссылку на голову из списка клонов.

        return new LinkedList(map.get(this.head));

    }

}

  
// Класс водителя

class Main

{

    // Основной метод.

    public static void main(String[] args)

    {

        // Подталкиваем данные в связанном списке.

        LinkedList list = new LinkedList(new Node(5));

        list.push(4);

        list.push(3);

        list.push(2);

        list.push(1);

  

        // Настройка случайных ссылок.

        list.head.random = list.head.next.next;

        list.head.next.random =

            list.head.next.next.next;

        list.head.next.next.random =

            list.head.next.next.next.next;

        list.head.next.next.next.random =

            list.head.next.next.next.next.next;

        list.head.next.next.next.next.random =

            list.head.next;

  

        // Создание клона исходного связанного списка.

        LinkedList clone = list.clone();

  

        // Распечатать исходный и клонированный связанный список.

        System.out.println("Original linked list");

        list.print();

        System.out.println("\nCloned linked list");

        clone.print();

    }

}


Выход:

Original linked list
Data = 1, Random data = 3
Data = 2, Random data = 4
Data = 3, Random data = 5
Data = 4, Random data = -1
Data = 5, Random data = 2

Cloned linked list
Data = 1, Random data = 3
Data = 2, Random data = 4
Data = 3, Random data = 5
Data = 4, Random data = -1
Data = 5, Random data = 2

Временная сложность: O (n)
Вспомогательное пространство: O (n)

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

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

Клонировать связанный список со следующим и случайным указателем | Набор 2

0.00 (0%) 0 votes