Рубрики

Напишите функцию, чтобы получить точку пересечения двух связанных списков | Набор 2

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

Приведенная выше диаграмма показывает пример с двумя связанными списками, имеющими 15 в качестве точки пересечения.

Подход: можно заметить, что число узлов при прохождении первого связанного списка, а затем от заголовка второго связанного списка до точки пересечения равно числу узлов, участвующих в прохождении второго связанного списка, а затем от заголовка Первый список до точки пересечения. Рассматривая приведенный выше пример, начните обход двух связанных списков с помощью двух указателей curr1 и curr2, указывающих соответственно на заголовки указанных связанных списков.

  1. Если curr1! = Null, обновите его, чтобы он указывал на следующий узел, иначе он обновляется, чтобы указывать на первый узел второго списка.
  2. Если curr2! = Null, обновите его, чтобы он указывал на следующий узел, иначе он обновляется, чтобы указывать на первый узел первого списка.
  3. Повторите вышеуказанные шаги, пока curr1 не равен curr2 .

Два указателя curr1 и curr2 теперь будут указывать на один и тот же узел, то есть на точку слияния.

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

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

  
// узел списка ссылок

struct Node {

    int data;

    Node* next;

};

  
// Функция для получения точки пересечения
// из указанных связанных списков

int getIntersectionNode(Node* head1, Node* head2)

{

    Node *curr1 = head1, *curr2 = head2;

  

    // Хотя оба указателя не равны

    while (curr1 != curr2) {

  

        // Если первый указатель нулевой, то

        // установить его так, чтобы он указывал на заголовок

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

        if (curr1 == NULL) {

            curr1 = head2;

        }

  

        // Остальное указывает на следующий узел

        else {

            curr1 = curr1->next;

        }

  

        // Если второй указатель нулевой, то

        // установить его так, чтобы он указывал на заголовок

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

        if (curr2 == NULL) {

            curr2 = head1;

        }

  

        // Остальное указывает на следующий узел

        else {

            curr2 = curr2->next;

        }

    }

  

    // Возвращаем узел пересечения

    return curr1->data;

}

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

int main()

{

    / *

    Создайте два связанных списка

  

    1-й связанный список 3-> 6-> 9-> 15-> 30

    2-й связанный список 10-> 15-> 30

      

    15 - точка пересечения

    * /

  

    Node* newNode;

    Node* head1 = new Node();

    head1->data = 10;

    Node* head2 = new Node();

    head2->data = 3;

    newNode = new Node();

    newNode->data = 6;

    head2->next = newNode;

    newNode = new Node();

    newNode->data = 9;

    head2->next->next = newNode;

    newNode = new Node();

    newNode->data = 15;

    head1->next = newNode;

    head2->next->next->next = newNode;

    newNode = new Node();

    newNode->data = 30;

    head1->next->next = newNode;

    head1->next->next->next = NULL;

  

    // Печать узла пересечения

    cout << getIntersectionNode(head1, head2);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

  
// узел списка ссылок

static class Node 

{

    int data;

    Node next;

};

  
// Функция для получения точки пересечения
// из указанных связанных списков

static int getIntersectionNode(Node head1, Node head2)

{

    Node curr1 = head1, curr2 = head2;

  

    // Хотя оба указателя не равны

    while (curr1 != curr2) 

    {

  

        // Если первый указатель нулевой, то

        // установить его так, чтобы он указывал на заголовок

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

        if (curr1 == null)

        {

            curr1 = head2;

        }

  

        // Остальное указывает на следующий узел

        else 

        {

            curr1 = curr1.next;

        }

  

        // Если второй указатель нулевой, то

        // установить его так, чтобы он указывал на заголовок

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

        if (curr2 == null)

        {

            curr2 = head1;

        }

  

        // Остальное указывает на следующий узел

        else

        {

            curr2 = curr2.next;

        }

    }

  

    // Возвращаем узел пересечения

    return curr1.data;

}

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

public static void main(String[] args)

{

    / *

    Создайте два связанных списка

  

    1-й связанный список - 3.6.9.15.30

    2-й связанный список 10.15.30

      

    15 - точка пересечения

    * /

  

    Node newNode;

    Node head1 = new Node();

    head1.data = 10;

    Node head2 = new Node();

    head2.data = 3;

    newNode = new Node();

    newNode.data = 6;

    head2.next = newNode;

    newNode = new Node();

    newNode.data = 9;

    head2.next.next = newNode;

    newNode = new Node();

    newNode.data = 15;

    head1.next = newNode;

    head2.next.next.next = newNode;

    newNode = new Node();

    newNode.data = 30;

    head1.next.next = newNode;

    head1.next.next.next = null;

  

    // Печать узла пересечения

    System.out.print(getIntersectionNode(head1, head2));

}
}

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

C #

// C # реализация подхода

using System;

  

class GFG

{

  
// узел списка ссылок

public class Node 

{

    public int data;

    public Node next;

};

  
// Функция для получения точки пересечения
// из указанных связанных списков

static int getIntersectionNode(Node head1, 

                               Node head2)

{

    Node curr1 = head1, curr2 = head2;

  

    // Хотя оба указателя не равны

    while (curr1 != curr2) 

    {

  

        // Если первый указатель нулевой, то

        // установить его так, чтобы он указывал на заголовок

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

        if (curr1 == null)

        {

            curr1 = head2;

        }

  

        // Остальное указывает на следующий узел

        else

        {

            curr1 = curr1.next;

        }

  

        // Если второй указатель нулевой, то

        // установить его так, чтобы он указывал на заголовок

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

        if (curr2 == null)

        {

            curr2 = head1;

        }

  

        // Остальное указывает на следующий узел

        else

        {

            curr2 = curr2.next;

        }

    }

  

    // Возвращаем узел пересечения

    return curr1.data;

}

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

public static void Main(String[] args)

{

    / *

    Создайте два связанных списка

  

    1-й связанный список - 3.6.9.15.30

    2-й связанный список 10.15.30

      

    15 - точка пересечения

    * /

    Node newNode;

    Node head1 = new Node();

    head1.data = 10;

    Node head2 = new Node();

    head2.data = 3;

    newNode = new Node();

    newNode.data = 6;

    head2.next = newNode;

    newNode = new Node();

    newNode.data = 9;

    head2.next.next = newNode;

    newNode = new Node();

    newNode.data = 15;

    head1.next = newNode;

    head2.next.next.next = newNode;

    newNode = new Node();

    newNode.data = 30;

    head1.next.next = newNode;

    head1.next.next.next = null;

  

    // Печать узла пересечения

    Console.Write(getIntersectionNode(head1, head2));

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

15

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

Напишите функцию, чтобы получить точку пересечения двух связанных списков | Набор 2

0.00 (0%) 0 votes