Hay dos listas enlazadas individualmente en un sistema. Por algún error de programación, el Node final de una de las listas vinculadas se vinculó a la segunda lista, formando una lista en forma de Y invertida. Escriba un programa para obtener el punto donde ambas listas enlazadas se fusionan.
Ejemplos:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
^
|
7 -> 8 -> 9
Output: 4
Input: 13 -> 14 -> 5 -> 6
^
|
10 -> 2 -> 3 -> 4
Output: 14
Requisitos previos: escribir una función para obtener el punto de intersección de dos listas enlazadas
Enfoque: tome dos punteros para los encabezados de ambas listas vinculadas. Si uno de ellos llega al final antes, utilícelo moviéndolo al principio de la otra lista. Una vez que ambos pasen por la reasignación, estarán a la misma distancia del punto de colisión.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
// Function to return the intersection point
// of the two linked lists head1 and head2
int getIntesectionNode(Node* head1, Node* head2)
{
Node* current1 = head1;
Node* current2 = head2;
// If one of the head is NULL
if (!current1 or !current2)
return -1;
// Continue until we find intersection node
while (current1 and current2
and current1 != current2) {
current1 = current1->next;
current2 = current2->next;
// If we get intersection node
if (current1 == current2)
return current1->data;
// If one of them reaches end
if (!current1)
current1 = head2;
if (!current2)
current2 = head1;
}
return current1->data;
}
// Driver code
int main()
{
/*
Create two linked lists
1st 3->6->9->15->30
2nd 10->15->30
15 is the intersection point
*/
Node* newNode;
// Addition of new nodes
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 << getIntesectionNode(head1, head2);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
};
// Function to return the intersection point
// of the two linked lists head1 and head2
static int getIntesectionNode(Node head1, Node head2)
{
Node current1 = head1;
Node current2 = head2;
// If one of the head is null
if (current1 == null || current2 == null )
return -1;
// Continue until we find intersection node
while (current1 != null && current2 != null
&& current1 != current2)
{
current1 = current1.next;
current2 = current2.next;
// If we get intersection node
if (current1 == current2)
return current1.data;
// If one of them reaches end
if (current1 == null )
current1 = head2;
if (current2 == null )
current2 = head1;
}
return current1.data;
}
// Driver code
public static void main(String[] args)
{
/*
Create two linked lists
1st 3.6.9.15.30
2nd 10.15.30
15 is the intersection point
*/
Node newNode;
// Addition of new nodes
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(getIntesectionNode(head1, head2));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach ''' Link list node ''' class new_Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None # Function to return the intersection point # of the two linked lists head1 and head2 def getIntesectionNode(head1, head2): current1 = head1 current2 = head2 # If one of the head is None if (not current1 or not current2 ): return -1 # Continue until we find intersection node while (current1 and current2 and current1 != current2): current1 = current1.next current2 = current2.next # If we get intersection node if (current1 == current2): return current1.data # If one of them reaches end if (not current1): current1 = head2 if (not current2): current2 = head1 return current1.data # Driver code ''' Create two linked lists 1st 3.6.9.15.30 2nd 10.15.30 15 is the intersection po ''' # Addition of newNodes head1 = new_Node(10) head2 = new_Node(3) newNode = new_Node(6) head2.next = newNode newNode = new_Node(9) head2.next.next = newNode newNode = new_Node(15) head1.next = newNode head2.next.next.next = newNode newNode = new_Node(30) head1.next.next = newNode head1.next.next.next = None print(getIntesectionNode(head1, head2)) # This code is contributed by shubhamsingh10
C#
// C# implementation of the approach
using System;
class GFG
{
/* Link list node */
class Node
{
public int data;
public Node next;
};
// Function to return the intersection point
// of the two linked lists head1 and head2
static int getIntesectionNode(Node head1, Node head2)
{
Node current1 = head1;
Node current2 = head2;
// If one of the head is null
if (current1 == null || current2 == null )
return -1;
// Continue until we find intersection node
while (current1 != null && current2 != null
&& current1 != current2)
{
current1 = current1.next;
current2 = current2.next;
// If we get intersection node
if (current1 == current2)
return current1.data;
// If one of them reaches end
if (current1 == null )
current1 = head2;
if (current2 == null )
current2 = head1;
}
return current1.data;
}
// Driver code
public static void Main(String[] args)
{
/*
Create two linked lists
1st 3.6.9.15.30
2nd 10.15.30
15 is the intersection point
*/
Node newNode;
// Addition of new nodes
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(getIntesectionNode(head1, head2));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
/* Link list node */
class Node {
constructor()
{
this.data = 0;
this.next = null;
}
};
// Function to return the intersection point
// of the two linked lists head1 and head2
function getIntesectionNode(head1, head2)
{
var current1 = head1;
var current2 = head2;
// If one of the head is null
if (!current1 || !current2)
return -1;
// Continue until we find intersection node
while (current1 && current2
&& current1 != current2) {
current1 = current1.next;
current2 = current2.next;
// If we get intersection node
if (current1 == current2)
return current1.data;
// If one of them reaches end
if (!current1)
current1 = head2;
if (!current2)
current2 = head1;
}
return current1.data;
}
// Driver code
/*
Create two linked lists
1st 3.6.9.15.30
2nd 10.15.30
15 is the intersection point
*/
var newNode;
// Addition of new nodes
var head1 = new Node();
head1.data = 10;
var 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;
document.write( getIntesectionNode(head1, head2));
// This code is contributed by noob2000.
</script>
Producción:
15
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA