There are two singly linked lists in a system. By some programming error, the end node of one of the linked lists got linked to the second list, forming an inverted Y-shaped list. Write a program to get the point where two linked lists merge.
Intersection Point of Two Linked Lists
The above diagram shows an example with two linked lists having 15 as intersection points.
Method 1(Simply use two loops):
Use 2 nested for loops. The outer loop will be for each node of the 1st list and the inner loop will be for the 2nd list. In the inner loop, check if any of the nodes of the 2nd list is the same as the current node of the first linked list. The time complexity of this method will be O(M * N) where m and n are the numbers of nodes in two lists.
Below is the code for the above approach:
C++
// C++ program to get intersection point of two linked list#include <bits/stdc++.h>using namespace std;/* Link list node */class Node {public: int data; Node* next;};/* function to get the intersection point of two linkedlists head1 and head2 */Node* getIntesectionNode(Node* head1, Node* head2){ while (head2) { Node* temp = head1; while (temp) { // if both Nodes are same if (temp == head2) return head2; temp = temp->next; } head2 = head2->next; } // intersection is not present between the lists return NULL;}// Driver Codeint 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; Node* intersectionPoint = getIntesectionNode(head1, head2); if (!intersectionPoint) cout << " No Intersection Point \n"; else cout << "Intersection Point: " << intersectionPoint->data << endl;}// This code is contributed by Tapesh(tapeshdua420) |
C
// C program to get intersection point of two linked list#include <stdio.h>#include <stdlib.h>/* Link list node */typedef struct Node { int data; struct Node* next;} Node;/* function to get the intersection point of two linkedlists head1 and head2 */Node* getIntesectionNode(Node* head1, Node* head2){ while (head2) { Node* temp = head1; while (temp) { // if both Nodes are same if (temp == head2) return head2; temp = temp->next; } head2 = head2->next; } // intersection is not present between the lists return NULL;}// Driver Codeint 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 = (Node*)malloc(sizeof(Node)); head1->data = 10; Node* head2 = (Node*)malloc(sizeof(Node)); head2->data = 3; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 6; head2->next = newNode; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 9; head2->next->next = newNode; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 15; head1->next = newNode; head2->next->next->next = newNode; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 30; head1->next->next = newNode; head1->next->next->next = NULL; Node* intersectionPoint = getIntesectionNode(head1, head2); if (!intersectionPoint) printf(" No Intersection Point \n"); else printf("Intersection Point: %d\n", intersectionPoint->data);}// This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java Program to get intersection point of two linked// lists.import java.util.*;import java.io.*;class GFG { static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* function to get the intersection point of two linked lists head1 and head2 */ public Node getIntersectionNode(Node head1, Node head2) { while (head2 != null) { Node temp = head1; while (temp != null) { // if both Nodes are same if (temp == head2) { return head2; } temp = temp.next; } head2 = head2.next; } // If intersection is not present between the lists, // return NULL. return null; } public static void main(String[] args) { GFG list = new GFG(); Node head1, head2; /* Create two linked lists 1st 3->6->9->15->30 2nd 10->15->30 15 is the intersection point */ head1 = new Node(10); head2 = new Node(3); Node 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 = null; Node intersectionPoint = list.getIntersectionNode(head1, head2); if (intersectionPoint == null) { System.out.print(" No Intersection Point \n"); } else { System.out.print("Intersection Point: " + intersectionPoint.data); } }}// This code is contributed by lokesh (lokeshmvs21). |
Python3
# Python program to get intersection point of two linked list# Link list nodeclass Node: def __init__(self, data): self.data = data self.next = None# function to get the intersection point of two linked lists head1 and headdef getIntersectionNode(head1, head2): while head2: temp = head1 while temp: # if both Nodes are same if temp == head2: return head2 temp = temp.next head2 = head2.next # intersection is not present between the lists return None# Driver Codeif __name__ == '__main__': ''' Create two linked lists 1st 3->6->9->15->30 2nd 10->15->30 15 is the intersection point ''' newNode = Node(10) head1 = newNode newNode = Node(3) head2 = newNode newNode = Node(6) head2.next = newNode newNode = Node(9) head2.next.next = newNode newNode = Node(15) head1.next = newNode head2.next.next.next = newNode newNode = Node(30) head1.next.next = newNode intersectionPoint = getIntersectionNode(head1, head2) if not intersectionPoint: print(" No Intersection Point ") else: print("Intersection Point:", intersectionPoint.data)# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# program to get intersection point of two linked// lists.using System;class GFG { public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /* function to get the intersection point of two linked * lists head1 and head2 */ public Node getIntersectionNode(Node head1, Node head2) { while (head2 != null) { Node temp = head1; while (temp != null) { // if both Nodes are same if (temp == head2) { return head2; } temp = temp.next; } head2 = head2.next; } // If intersection is not present between the lists, // return NULL. return null; } public static void Main(string[] args) { GFG list = new GFG(); Node head1, head2; /* Create two linked lists 1st 3->6->9->15->30 2nd 10->15->30 15 is the intersection point */ head1 = new Node(10); head2 = new Node(3); Node 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 = null; Node intersectionPoint = list.getIntersectionNode(head1, head2); if (intersectionPoint == null) { Console.Write(" No Intersection Point \n"); } else { Console.Write("Intersection Point: " + intersectionPoint.data); } }}// This code is contributed by Tapesh(tapeshdua420). |
Javascript
// JS code for finding intersection pointclass Node { constructor(d) { this.data = d; this.next = null; }}function getIntesectionNode(head1, head2) { while (head2) { let temp = head1; while (temp) { if (temp == head2) { return head2; } temp = temp.next; } head2 = head2.next; } return null;}let newNode = new Node();let head1 = new Node();head1.data = 10;let 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;let intersectionPoint = getIntesectionNode(head1, head2);if (!intersectionPoint) console.log(" No Intersection Point");else console.log("Intersection Point: ", intersectionPoint.data);// This code is contributed by adityamaharshi21 |
Output
Intersection Point: 15
Time Complexity: O(m*n), where m and n are number of nodes in two linked list.
Auxiliary Space: O(1), Constant Space is used.
Method 2 (Mark Visited Nodes):
This solution requires modifications to the basic linked list data structure. Have a visited flag with each node. Traverse the first linked list and keep marking visited nodes. Now traverse the second linked list, If you see a visited node again then there is an intersection point, return the intersecting node. This solution works in O(m+n) but requires additional information with each node. A variation of this solution that doesn’t require modification to the basic data structure can be implemented using a hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in the hash then return the intersecting node.
C++
// C++ Program for the above approach#include<bits/stdc++.h>using namespace std;struct Node{ int data; Node* next; bool visited; Node(int data){ this->data = data; this->next = NULL; this->visited = false; }};int getIntersectNode(Node* head1, Node* head2){ Node* temp1 = head1; while(temp1 != NULL){ temp1->visited = true; temp1 = temp1->next; } temp1 = head2; while(temp1 != NULL){ if(temp1->visited) return temp1->data; else temp1->visited = true; temp1 = temp1->next; }}// driver programint main(){ Node* head1 = new Node(1); head1->next = new Node(2); head1->next->next = new Node(3); head1->next->next->next = new Node(4); head1->next->next->next->next = new Node(5); head1->next->next->next->next->next = new Node(6); head1->next->next->next->next->next->next = new Node(7); // list 2 Node* head2 = new Node(10); head2->next = new Node(9); head2->next->next = new Node(8); head2->next->next->next = head1->next->next->next; cout<<"The node of intersection is : "<<getIntersectNode(head1, head2); return 0;}// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Java
// package whatever //do not write package name here import java.io.*;// Java Program to get intersection point of two linked listpublic class LinkedList{ static class Node{ int data; Node next; boolean visited; Node(int d){ data = d; next = null; visited = false; } } static int getIntersectNode(Node head1, Node head2){ Node temp1 = head1; while(temp1 != null){ temp1.visited = true; temp1= temp1.next; } temp1 = head2; while(temp1 != null){ if(temp1.visited){ return temp1.data; } else{ temp1.visited = true; } temp1 = temp1.next; } return -1; } public static void main(String[] args){ Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); // list 2 Node head2 = new Node(10); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next; System.out.print("The node of intersection is : " + getIntersectNode(head1, head2)); }} |
Python
# Python program for the above approachclass Node: def __init__(self, data): self.data = data self.next = None self.visited = False def getIntersectNode(head1, head2): temp1 = head1 while(temp1 is not None): temp1.visited = True temp1 = temp1.next temp1 = head2 while(temp1 is not None): if(temp1.visited): return temp1.data else: temp1.visited = True temp1 = temp1.next # driver program to test above functionhead1 = Node(1);head1.next = Node(2);head1.next.next = Node(3);head1.next.next.next = Node(4);head1.next.next.next.next = Node(5);head1.next.next.next.next.next = Node(6);head1.next.next.next.next.next.next = Node(7);# list2head2 = Node(10);head2.next = Node(9);head2.next.next = Node(8);head2.next.next.next = head1.next.next.next; print("The node of intersection is : ")print(getIntersectNode(head1, head2)) |
C#
// C# Program to get intersection point of two linked// lists.using System;public class Node{ public int data; public Node next; public bool visited; public Node(int d){ data = d; next = null; visited = false; }}class GFG{ static int getIntersectNode(Node head1, Node head2){ Node temp1 = head1; while(temp1 != null){ temp1.visited = true; temp1 = temp1.next; } temp1 = head2; while(temp1 != null){ if(temp1.visited == true) return temp1.data; else temp1.visited = true; temp1 = temp1.next; } return -1; } public static void Main(string[] args){ // list1 Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); // list2 Node head2 = new Node(10); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next; Console.WriteLine("The node of intersection is : " + getIntersectNode(head1, head2)); }} |
Javascript
// JavaScript program for the above approachclass Node{ constructor(data){ this.data = data; this.next = null; this.visited = false; }}function getIntersectNode(head1, head2){ let temp1 = head1; while(temp1 != null){ temp1.visited = true; temp1 = temp1.next; } temp1 = head2; while(temp1 != null){ if(temp1.visited) return temp1.data; else temp1.visited = true; temp1 = temp1.next; }}// driver program to test above functionlet head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); // list 2 let head2 = new Node(10); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next; console.log("The node of intersection is : " + getIntersectNode(head1, head2)); |
Output
The node of intersection is : 4
Time Complexity:
The time complexity of the getIntersectNode function is O(m+n) where m and n are the lengths of the input linked lists. This is because in the worst case scenario, we need to traverse both lists once to mark visited nodes, and then traverse the second list to find the first node that has already been visited.
Auxiliary space:
The auxiliary space required by the program is O(max(m,n)), which is the maximum length of the input linked lists. This is because we are marking visited nodes in the linked lists using a boolean flag, and we need to do this for the entire length of the longer list.
Method 3(Using the difference in node counts)
- Get the count of the nodes in the first list, let the count be c1.
- Get the count of the nodes in the second list, let the count be c2.
- Get the difference of counts d = abs(c1 – c2)
- Now traverse the bigger list from the first node to d nodes so that from here onwards both the lists have an equal no of nodes
- Then we can traverse both lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)
Below image is a dry run of the above approach:
Step 1: Traverse the bigger list from the first node to d nodes so that from here onwards both the lists have an equal no of nodes
Step 1
Step 2: Traverse both lists in parallel till we come across a common node
Step 2
Below is the implementation of the above approach :
C++
// C++ program to get intersection point of two linked list#include <bits/stdc++.h>using namespace std;/* Link list node */class Node {public: int data; Node* next;};/* Function to get the counts of node in a linked list */int getCount(Node* head);/* function to get the intersection point of two linked lists head1 and head2 where head1 has d more nodes than head2 */int _getIntesectionNode(int d, Node* head1, Node* head2);/* function to get the intersection point of two linked lists head1 and head2 */int getIntesectionNode(Node* head1, Node* head2){ // Count the number of nodes in // both the linked list int c1 = getCount(head1); int c2 = getCount(head2); int d; // If first is greater if (c1 > c2) { d = c1 - c2; return _getIntesectionNode(d, head1, head2); } else { d = c2 - c1; return _getIntesectionNode(d, head2, head1); }}/* function to get the intersection point of two linked lists head1 and head2 where head1 has d more nodes than head2 */int _getIntesectionNode(int d, Node* head1, Node* head2){ // Stand at the starting of the bigger list Node* current1 = head1; Node* current2 = head2; // Move the pointer forward for (int i = 0; i < d; i++) { if (current1 == NULL) { return -1; } current1 = current1->next; } // Move both pointers of both list till they // intersect with each other while (current1 != NULL && current2 != NULL) { if (current1 == current2) return current1->data; // Move both the pointers forward current1 = current1->next; current2 = current2->next; } return -1;}/* Takes head pointer of the linked list and returns the count of nodes in the list */int getCount(Node* head){ Node* current = head; // Counter to store count of nodes int count = 0; // Iterate till NULL while (current != NULL) { // Increase the counter count++; // Move the Node ahead current = current->next; } return count;}// Driver Codeint 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 << "The node of intersection is " << getIntesectionNode(head1, head2);}// This code is contributed by rathbhupendra |
C
// C program to get intersection point of two linked list#include <stdio.h>#include <stdlib.h>/* Link list node */struct Node { int data; struct Node* next;};/* Function to get the counts of node in a linked list */int getCount(struct Node* head);/* function to get the intersection point of two linked lists head1 and head2 where head1 has d more nodes than head2 */int _getIntesectionNode(int d, struct Node* head1, struct Node* head2);/* function to get the intersection point of two linked lists head1 and head2 */int getIntesectionNode(struct Node* head1, struct Node* head2){ int c1 = getCount(head1); int c2 = getCount(head2); int d; if (c1 > c2) { d = c1 - c2; return _getIntesectionNode(d, head1, head2); } else { d = c2 - c1; return _getIntesectionNode(d, head2, head1); }}/* function to get the intersection point of two linked lists head1 and head2 where head1 has d more nodes than head2 */int _getIntesectionNode(int d, struct Node* head1, struct Node* head2){ int i; struct Node* current1 = head1; struct Node* current2 = head2; for (i = 0; i < d; i++) { if (current1 == NULL) { return -1; } current1 = current1->next; } while (current1 != NULL && current2 != NULL) { if (current1 == current2) return current1->data; current1 = current1->next; current2 = current2->next; } return -1;}/* Takes head pointer of the linked list and returns the count of nodes in the list */int getCount(struct Node* head){ struct Node* current = head; int count = 0; while (current != NULL) { count++; current = current->next; } return count;}/* IGNORE THE BELOW LINES OF CODE. THESE LINES ARE JUST TO QUICKLY TEST THE ABOVE FUNCTION */int main(){ /* Create two linked lists 1st 3->6->9->15->30 2nd 10->15->30 15 is the intersection point */ struct Node* newNode; struct Node* head1 = (struct Node*)malloc(sizeof(struct Node)); head1->data = 10; struct Node* head2 = (struct Node*)malloc(sizeof(struct Node)); head2->data = 3; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 6; head2->next = newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 9; head2->next->next = newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 15; head1->next = newNode; head2->next->next->next = newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 30; head1->next->next = newNode; head1->next->next->next = NULL; printf("\n The node of intersection is %d \n", getIntesectionNode(head1, head2)); getchar();} |
Java
// Java program to get intersection point of two linked listclass LinkedList { static Node head1, head2; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /*function to get the intersection point of two linked lists head1 and head2 */ int getNode() { int c1 = getCount(head1); int c2 = getCount(head2); int d; if (c1 > c2) { d = c1 - c2; return _getIntesectionNode(d, head1, head2); } else { d = c2 - c1; return _getIntesectionNode(d, head2, head1); } } /* function to get the intersection point of two linked lists head1 and head2 where head1 has d more nodes than head2 */ int _getIntesectionNode(int d, Node node1, Node node2) { int i; Node current1 = node1; Node current2 = node2; for (i = 0; i < d; i++) { if (current1 == null) { return -1; } current1 = current1.next; } while (current1 != null && current2 != null) { if (current1.data == current2.data) { return current1.data; } current1 = current1.next; current2 = current2.next; } return -1; } /*Takes head pointer of the linked list and returns the count of nodes in the list */ int getCount(Node node) { Node current = node; int count = 0; while (current != null) { count++; current = current.next; } return count; } public static void main(String[] args) { LinkedList list = new LinkedList(); // creating first linked list list.head1 = new Node(3); list.head1.next = new Node(6); list.head1.next.next = new Node(9); list.head1.next.next.next = new Node(15); list.head1.next.next.next.next = new Node(30); // creating second linked list list.head2 = new Node(10); list.head2.next = new Node(15); list.head2.next.next = new Node(30); System.out.println("The node of intersection is " + list.getNode()); }}// This code has been contributed by Mayank Jaiswal |
Python3
# defining a node for LinkedListclass Node: def __init__(self,data): self.data=data self.next=None def getIntersectionNode(head1,head2): #finding the total number of elements in head1 LinkedList c1=getCount(head1) #finding the total number of elements in head2 LinkedList c2=getCount(head2) #Traverse the bigger node by 'd' so that from that node onwards, both LinkedList #would be having same number of nodes and we can traverse them together. if c1 > c2: d=c1-c2 return _getIntersectionNode(d,head1,head2) else: d=c2-c1 return _getIntersectionNode(d,head2,head1) def _getIntersectionNode(d,head1,head2): current1=head1 current2=head2 for i in range(d): if current1 is None: return -1 current1=current1.next while current1 is not None and current2 is not None: # Instead of values, we need to check if there addresses are same # because there can be a case where value is same but that value is #not an intersecting point. if current1 is current2: return current1.data # or current2.data ( the value would be same) current1=current1.next current2=current2.next # Incase, we are not able to find our intersecting point. return -1 #Function to get the count of a LinkedListdef getCount(node): cur=node count=0 while cur is not None: count+=1 cur=cur.next return count if __name__ == '__main__': # Creating two LinkedList # 1st one: 3->6->9->15->30 # 2nd one: 10->15->30 # We can see that 15 would be our intersection point # Defining the common node common=Node(15) #Defining first LinkedList head1=Node(3) head1.next=Node(6) head1.next.next=Node(9) head1.next.next.next=common head1.next.next.next.next=Node(30) # Defining second LinkedList head2=Node(10) head2.next=common head2.next.next=Node(30) print("The node of intersection is ",getIntersectionNode(head1,head2)) # The code is contributed by Ansh Gupta. |
C#
// C# program to get intersection point of two linked listusing System;class LinkedList { Node head1, head2; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /*function to get the intersection point of two linked lists head1 and head2 */ int getNode() { int c1 = getCount(head1); int c2 = getCount(head2); int d; if (c1 > c2) { d = c1 - c2; return _getIntesectionNode(d, head1, head2); } else { d = c2 - c1; return _getIntesectionNode(d, head2, head1); } } /* function to get the intersection point of two linked lists head1 and head2 where head1 has d more nodes than head2 */ int _getIntesectionNode(int d, Node node1, Node node2) { int i; Node current1 = node1; Node current2 = node2; for (i = 0; i < d; i++) { if (current1 == null) { return -1; } current1 = current1.next; } while (current1 != null && current2 != null) { if (current1.data == current2.data) { return current1.data; } current1 = current1.next; current2 = current2.next; } return -1; } /*Takes head pointer of the linked list and returns the count of nodes in the list */ int getCount(Node node) { Node current = node; int count = 0; while (current != null) { count++; current = current.next; } return count; } public static void Main(String[] args) { LinkedList list = new LinkedList(); // creating first linked list list.head1 = new Node(3); list.head1.next = new Node(6); list.head1.next.next = new Node(9); list.head1.next.next.next = new Node(15); list.head1.next.next.next.next = new Node(30); // creating second linked list list.head2 = new Node(10); list.head2.next = new Node(15); list.head2.next.next = new Node(30); Console.WriteLine("The node of intersection is " + list.getNode()); }}// This code is contributed by Arnab Kundu |
Javascript
<script>class Node{ constructor(item) { this.data=item; this.next=null; }}let head1,head2;function getNode(){ let c1 = getCount(head1); let c2 = getCount(head2); let d; if (c1 > c2) { d = c1 - c2; return _getIntesectionNode(d, head1, head2); } else { d = c2 - c1; return _getIntesectionNode(d, head2, head1); }}function _getIntesectionNode(d,node1,node2){ let i; let current1 = node1; let current2 = node2; for (i = 0; i < d; i++) { if (current1 == null) { return -1; } current1 = current1.next; } while (current1 != null && current2 != null) { if (current1.data == current2.data) { return current1.data; } current1 = current1.next; current2 = current2.next; } return -1;}function getCount(node){ let current = node; let count = 0; while (current != null) { count++; current = current.next; } return count;}head1 = new Node(3);head1.next = new Node(6);head1.next.next = new Node(9);head1.next.next.next = new Node(15);head1.next.next.next.next = new Node(30);// creating second linked listhead2 = new Node(10);head2.next = new Node(15);head2.next.next = new Node(30);document.write("The node of intersection is " + getNode());// This code is contributed by avanitrachhadiya2155</script> |
Output
The node of intersection is 15
Time Complexity: O(m+n)
Auxiliary Space: O(1)
Method 4(Make a circle in the first list)
Thanks to Saravanan Man for providing the below solution.
1. Traverse the first linked list(count the elements) and make a circular linked list. (Remember the last node so that we can break the circle later on).
2. Now view the problem as finding the loop in the second linked list. So the problem is solved.
3. Since we already know the length of the loop(size of the first linked list) we can traverse those many numbers of nodes in the second list, and then start another pointer from the beginning of the second list. we have to traverse until they are equal, and that is the required intersection point.
4. remove the circle from the linked list.
Time Complexity: O(m+n)
Auxiliary Space: O(1)
Method 5 (Reverse the first list and make equations)
Thanks to Saravanan Mani for providing this method.
1) Let X be the length of the first linked list until intersection point.
Let Y be the length of the second linked list until the intersection point.
Let Z be the length of the linked list from the intersection point to End of
the linked list including the intersection node.
We Have
X + Z = C1;
Y + Z = C2;
2) Reverse first linked list.
3) Traverse Second linked list. Let C3 be the length of second list - 1.
Now we have
X + Y = C3
We have 3 linear equations. By solving them, we get
X = (C1 + C3 – C2)/2;
Y = (C2 + C3 – C1)/2;
Z = (C1 + C2 – C3)/2;
WE GOT THE INTERSECTION POINT.
4) Reverse first linked list.
Advantage: No Comparison of pointers.
Disadvantage: Modifying linked list(Reversing list).
Time complexity: O(m+n)
Auxiliary Space: O(1)
Method 6 (Traverse both lists and compare addresses of last nodes) This method is only to detect if there is an intersection point or not. (Thanks to NeoTheSaviour for suggesting this)
1) Traverse the list 1, store the last node address 2) Traverse the list 2, store the last node address. 3) If nodes stored in 1 and 2 are same then they are intersecting.
Time Complexity: O(m+n)
Auxiliary Space: O(1)
Method 7 (Use Hashing)
Basically, we need to find a common node of two linked lists. So we hash all nodes of the first list and then check the second list.
1) Create an empty hash set.
2) Traverse the first linked list and insert all nodes’ addresses in the hash set.
3) Traverse the second list. For every node check if it is present in the hash set. If we find a node in the hash set, return the node.
C++
// C++ program to get intersection point of two linked list#include <iostream>#include <unordered_set>using namespace std;class Node{public: int data; Node* next; Node(int d) { data = d; next = NULL; }};// function to find the intersection point of two listsvoid MegeNode(Node* n1, Node* n2){ unordered_set<Node*> hs; while (n1 != NULL) { hs.insert(n1); n1 = n1->next; } while (n2) { if (hs.find(n2) != hs.end()) { cout << n2->data << endl; break; } n2 = n2->next; }}// function to print the listvoid Print(Node* n){ Node* curr = n; while(curr != NULL){ cout << curr->data << " "; curr = curr->next; } cout << endl;} int main() { // list 1 Node* n1 = new Node(1); n1->next = new Node(2); n1->next->next = new Node(3); n1->next->next->next = new Node(4); n1->next->next->next->next = new Node(5); n1->next->next->next->next->next = new Node(6); n1->next->next->next->next->next->next = new Node(7); // list 2 Node* n2 = new Node(10); n2->next = new Node(9); n2->next->next = new Node(8); n2->next->next->next = n1->next->next->next; Print(n1); Print(n2); MegeNode(n1,n2); return 0;} // This code is contributed by Upendra |
Java
// Java program to get intersection point of two linked listimport java.util.*;class Node { int data; Node next; Node(int d) { data = d; next = null; }}class LinkedListIntersect { public static void main(String[] args) { // list 1 Node n1 = new Node(1); n1.next = new Node(2); n1.next.next = new Node(3); n1.next.next.next = new Node(4); n1.next.next.next.next = new Node(5); n1.next.next.next.next.next = new Node(6); n1.next.next.next.next.next.next = new Node(7); // list 2 Node n2 = new Node(10); n2.next = new Node(9); n2.next.next = new Node(8); n2.next.next.next = n1.next.next.next; Print(n1); Print(n2); System.out.println(MegeNode(n1, n2).data); } // function to print the list public static void Print(Node n) { Node cur = n; while (cur != null) { System.out.print(cur.data + " "); cur = cur.next; } System.out.println(); } // function to find the intersection of two node public static Node MegeNode(Node n1, Node n2) { // define hashset HashSet<Node> hs = new HashSet<Node>(); while (n1 != null) { hs.add(n1); n1 = n1.next; } while (n2 != null) { if (hs.contains(n2)) { return n2; } n2 = n2.next; } return null; }} |
Python3
# Python program to get intersection # point of two linked listclass Node : def __init__(self, d): self.data = d; self.next = None;# Function to print the listdef Print(n): cur = n; while (cur != None) : print(cur.data, end=" "); cur = cur.next; print("");# Function to find the intersection of two nodedef MegeNode(n1, n2): # Define hashset hs = set(); while (n1 != None): hs.add(n1); n1 = n1.next; while (n2 != None): if (n2 in hs): return n2; n2 = n2.next; return None;# Driver code# list 1n1 = Node(1);n1.next = Node(2);n1.next.next = Node(3);n1.next.next.next = Node(4);n1.next.next.next.next = Node(5);n1.next.next.next.next.next = Node(6);n1.next.next.next.next.next.next = Node(7);# list 2n2 = Node(10);n2.next = Node(9);n2.next.next = Node(8);n2.next.next.next = n1.next.next.next;Print(n1);Print(n2);print(MegeNode(n1, n2).data);# This code is contributed by _saurabh_jaiswal |
C#
// C# program to get intersection point of two linked listusing System;using System.Collections.Generic; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; }}public class LinkedListIntersect{ public static void Main(String[] args) { // list 1 Node n1 = new Node(1); n1.next = new Node(2); n1.next.next = new Node(3); n1.next.next.next = new Node(4); n1.next.next.next.next = new Node(5); n1.next.next.next.next.next = new Node(6); n1.next.next.next.next.next.next = new Node(7); // list 2 Node n2 = new Node(10); n2.next = new Node(9); n2.next.next = new Node(8); n2.next.next.next = n1.next.next.next; Print(n1); Print(n2); Console.WriteLine(MegeNode(n1, n2).data); } // function to print the list public static void Print(Node n) { Node cur = n; while (cur != null) { Console.Write(cur.data + " "); cur = cur.next; } Console.WriteLine(); } // function to find the intersection of two node public static Node MegeNode(Node n1, Node n2) { // define hashset HashSet<Node> hs = new HashSet<Node>(); while (n1 != null) { hs.Add(n1); n1 = n1.next; } while (n2 != null) { if (hs.Contains(n2)) { return n2; } n2 = n2.next; } return null; }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to get intersection // point of two linked listclass Node { constructor(d) { this.data = d; this.next = null; }}// Function to print the listfunction Print(n){ let cur = n; while (cur != null) { document.write(cur.data + " "); cur = cur.next; } document.write("<br>");}// Function to find the intersection of two nodefunction MegeNode(n1, n2){ // Define hashset let hs = new Set(); while (n1 != null) { hs.add(n1); n1 = n1.next; } while (n2 != null) { if (hs.has(n2)) { return n2; } n2 = n2.next; } return null;}// Driver code// list 1let n1 = new Node(1);n1.next = new Node(2);n1.next.next = new Node(3);n1.next.next.next = new Node(4);n1.next.next.next.next = new Node(5);n1.next.next.next.next.next = new Node(6);n1.next.next.next.next.next.next = new Node(7);// list 2let n2 = new Node(10);n2.next = new Node(9);n2.next.next = new Node(8);n2.next.next.next = n1.next.next.next;Print(n1);Print(n2);document.write(MegeNode(n1, n2).data);// This code is contributed by rag2127</script> |
Output
1 2 3 4 5 6 7 10 9 8 4 5 6 7 4
The time complexity of this solution is O(n) where n is the length of the longer list. This is because we need to traverse both of the linked lists in order to find the intersection point. And space complexity is O(n) , because we are using unordered set.
Method 8( 2-pointer technique ):
Using Two pointers :
- Initialize two pointers ptr1 and ptr2 at head1 and head2.
- Traverse through the lists, one node at a time.
- When ptr1 reaches the end of a list, then redirect it to head2.
- similarly, when ptr2 reaches the end of a list, redirect it to the head1.
- Once both of them go through reassigning, they will be equidistant from
the collision point - If at any node ptr1 meets ptr2, then it is the intersection node.
- After the second iteration if there is no intersection node it returns NULL.
C++
// CPP program to print intersection of lists#include <bits/stdc++.h>using namespace std;/* Link list node */class Node {public: int data; Node* next;};// A utility function to return intersection nodeNode* intersectPoint(Node* head1, Node* head2){ // Maintaining two pointers ptr1 and ptr2 // at the head of A and B, Node* ptr1 = head1; Node* ptr2 = head2; // If any one of head is NULL i.e // no Intersection Point if (ptr1 == NULL || ptr2 == NULL) return NULL; // Traverse through the lists until they // reach Intersection node while (ptr1 != ptr2) { ptr1 = ptr1->next; ptr2 = ptr2->next; // If at any node ptr1 meets ptr2, then it is // intersection node.Return intersection node. if (ptr1 == ptr2) return ptr1; /* Once both of them go through reassigning, they will be equidistant from the collision point.*/ // When ptr1 reaches the end of a list, then // reassign it to the head2. if (ptr1 == NULL) ptr1 = head2; // When ptr2 reaches the end of a list, then // redirect it to the head1. if (ptr2 == NULL) ptr2 = head1; } return ptr1;}// Function to print intersection nodes// in a given linked listvoid print(Node* node){ if (node == NULL) cout << "NULL"; while (node->next != NULL) { cout << node->data << "->"; node = node->next; } cout << node->data;}// Driver codeint main(){ /* Create two linked lists 1st Linked list is 3->6->9->15->30 2nd Linked list is 10->15->30 15 30 are elements in the intersection list */ 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; Node* intersect_node = NULL; // Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2); cout << "INTERSEPOINT LIST :"; print(intersect_node); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
C
// c program to print intersection of lists#include <stdio.h>#include <stdlib.h>/* Link list node */typedef struct Node { int data; struct Node* next;}Node;// A utility function to return intersection nodeNode* intersectPoint(Node* head1, Node* head2){ // Maintaining two pointers ptr1 and ptr2 // at the head of A and B, Node* ptr1 = head1; Node* ptr2 = head2; // If any one of head is NULL i.e // no Intersection Point if (ptr1 == NULL || ptr2 == NULL) return NULL; // Traverse through the lists until they // reach Intersection node while (ptr1 != ptr2) { ptr1 = ptr1->next; ptr2 = ptr2->next; // If at any node ptr1 meets ptr2, then it is // intersection node.Return intersection node. if (ptr1 == ptr2) return ptr1; /* Once both of them go through reassigning, they will be equidistant from the collision point.*/ // When ptr1 reaches the end of a list, then // reassign it to the head2. if (ptr1 == NULL) ptr1 = head2; // When ptr2 reaches the end of a list, then // redirect it to the head1. if (ptr2 == NULL) ptr2 = head1; } return ptr1;}// Function to print intersection nodes// in a given linked listvoid print(Node* node){ if (node == NULL) printf("NULL"); while (node->next != NULL) { printf("%d->", node->data); node = node->next; } printf("%d", node->data);}// Driver codeint main(){ /* Create two linked lists 1st Linked list is 3->6->9->15->30 2nd Linked list is 10->15->30 15 30 are elements in the intersection list */ Node* newNode; Node* head1 = (Node*)malloc(sizeof(Node)); head1->data = 10; Node* head2 = (Node*)malloc(sizeof(Node)); head2->data = 3; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 6; head2->next = newNode; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 9; head2->next->next = newNode; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 15; head1->next = newNode; head2->next->next->next = newNode; newNode = (Node*)malloc(sizeof(Node)); newNode->data = 30; head1->next->next = newNode; head1->next->next->next = NULL; Node* intersect_node = NULL; // Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2); printf("INTERSEPOINT LIST :"); print(intersect_node); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
Java
// JAVA program to print intersection of listsimport java.util.*;class GFG{/* Link list node */static class Node { int data; Node next;};// A utility function to return intersection nodestatic Node intersectPoint(Node head1, Node head2){ // Maintaining two pointers ptr1 and ptr2 // at the head of A and B, Node ptr1 = head1; Node ptr2 = head2; // If any one of head is null i.e // no Intersection Point if (ptr1 == null || ptr2 == null) { return null; } // Traverse through the lists until they // reach Intersection node while (ptr1 != ptr2) { ptr1 = ptr1.next; ptr2 = ptr2.next; // If at any node ptr1 meets ptr2, then it is // intersection node.Return intersection node. if (ptr1 == ptr2) { return ptr1; } /* Once both of them go through reassigning, they will be equidistant from the collision point.*/ // When ptr1 reaches the end of a list, then // reassign it to the head2. if (ptr1 == null) { ptr1 = head2; } // When ptr2 reaches the end of a list, then // redirect it to the head1. if (ptr2 == null) { ptr2 = head1; } } return ptr1;}// Function to print intersection nodes// in a given linked liststatic void print(Node node){ if (node == null) System.out.print("null"); while (node.next != null) { System.out.print(node.data+ "."); node = node.next; } System.out.print(node.data);} // Driver codepublic static void main(String[] args){ /* Create two linked lists 1st Linked list is 3.6.9.15.30 2nd Linked list is 10.15.30 15 30 are elements in the intersection list */ 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; Node intersect_node = null; // Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2); System.out.print("INTERSEPOINT LIST :"); print(intersect_node);}}// This code is contributed by umadevi9616. |
Python3
# Python3 program to print intersection of lists# Link list node class Node: def __init__(self, data = 0, next = None): self.data = data self.next = next# A utility function to return intersection nodedef intersectPoint(head1, head2): # Maintaining two pointers ptr1 and ptr2 # at the head of A and B, ptr1 = head1 ptr2 = head2 # If any one of head is None i.e # no Intersection Point if (ptr1 == None or ptr2 == None): return None # Traverse through the lists until they # reach Intersection node while (ptr1 != ptr2): ptr1 = ptr1.next ptr2 = ptr2.next # If at any node ptr1 meets ptr2, then it is # intersection node.Return intersection node. if (ptr1 == ptr2): return ptr1 # Once both of them go through reassigning, # they will be equidistant from the collision point. # When ptr1 reaches the end of a list, then # reassign it to the head2. if (ptr1 == None): ptr1 = head2 # When ptr2 reaches the end of a list, then # redirect it to the head1. if (ptr2 == None): ptr2 = head1 return ptr1# Function to print intersection nodes# in a given linked listdef Print(node): if (node == None): print("None") while (node.next != None): print(node.data,end="->") node = node.next print(node.data)# Driver code# Create two linked lists# 1st Linked list is 3->6->9->15->30# 2nd Linked list is 10->15->30# 15 30 are elements in the intersection listhead1 = Node()head1.data = 10head2 = Node()head2.data = 3newNode = Node()newNode.data = 6head2.next = newNodenewNode = Node()newNode.data = 9head2.next.next = newNodenewNode = Node()newNode.data = 15head1.next = newNodehead2.next.next.next = newNodenewNode = Node()newNode.data = 30head1.next.next = newNodehead1.next.next.next = Noneintersect_node = None # Find the intersection node of two linked listsintersect_node = intersectPoint(head1, head2)print("INTERSEPOINT LIST :",end="")Print(intersect_node)# This code is contributed by shinjanpatra |
C#
// C# program to print intersection of listsusing System;public class GFG { /* Link list node */ public class Node { public int data; public Node next; }; // A utility function to return intersection node static Node intersectPoint(Node head1, Node head2) { // Maintaining two pointers ptr1 and ptr2 // at the head of A and B, Node ptr1 = head1; Node ptr2 = head2; // If any one of head is null i.e // no Intersection Point if (ptr1 == null || ptr2 == null) { return null; } // Traverse through the lists until they // reach Intersection node while (ptr1 != ptr2) { ptr1 = ptr1.next; ptr2 = ptr2.next; // If at any node ptr1 meets ptr2, then it is // intersection node.Return intersection node. if (ptr1 == ptr2) { return ptr1; } /* * Once both of them go through reassigning, they will be equidistant from the * collision point. */ // When ptr1 reaches the end of a list, then // reassign it to the head2. if (ptr1 == null) { ptr1 = head2; } // When ptr2 reaches the end of a list, then // redirect it to the head1. if (ptr2 == null) { ptr2 = head1; } } return ptr1; } // Function to print intersection nodes // in a given linked list static void print(Node node) { if (node == null) Console.Write("null"); while (node.next != null) { Console.Write(node.data + "->"); node = node.next; } Console.Write(node.data); } // Driver code public static void Main(String[] args) { /* * Create two linked lists * * 1st Linked list is 3.6.9.15.30 2nd Linked list is 10.15.30 * * 15 30 are elements in the intersection list */ 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; Node intersect_node = null; // Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2); Console.Write("INTERSEPOINT LIST :"); print(intersect_node); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program to print intersection of lists/* Link list node */class Node { constructor() { this.data = null; this.next = null; }};// A utility function to return intersection nodefunction intersectPoint(head1, head2) { // Maintaining two pointers ptr1 and ptr2 // at the head of A and B, let ptr1 = head1; let ptr2 = head2; // If any one of head is null i.e // no Intersection Point if (ptr1 == null || ptr2 == null) { return null; } // Traverse through the lists until they // reach Intersection node while (ptr1 != ptr2) { ptr1 = ptr1.next; ptr2 = ptr2.next; // If at any node ptr1 meets ptr2, then it is // intersection node.Return intersection node. if (ptr1 == ptr2) { return ptr1; } /* Once both of them go through reassigning, they will be equidistant from the collision point.*/ // When ptr1 reaches the end of a list, then // reassign it to the head2. if (ptr1 == null) { ptr1 = head2; } // When ptr2 reaches the end of a list, then // redirect it to the head1. if (ptr2 == null) { ptr2 = head1; } } return ptr1;}// Function to print intersection nodes// in a given linked listfunction print(node) { if (node == null) document.write("null"); while (node.next != null) { document.write(node.data + "->"); node = node.next; } document.write(node.data);}// Driver code/*Create two linked lists1st Linked list is 3.6.9.15.302nd Linked list is 10.15.3015 30 are elements in the intersection list*/let newNode;let head1 = new Node();head1.data = 10;let 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;let intersect_node = null;// Find the intersection node of two linked listsintersect_node = intersectPoint(head1, head2);document.write("INTERSEPOINT LIST :");print(intersect_node);// This code is contributed by Saurabh Jaiswal</script> |
Output
INTERSEPOINT LIST :15->30
Time complexity : O( m + n )
Auxiliary Space: O(1)
Method 9 : Using the 2-stack approach :
- Create 2 stacks.
- Iterate both the lists till the end and keep on adding the nodes of the list to the respective stack.
- If the last nodes are not equal. return saying no intersection.
- Iteratively check the stack tops. If equal, pop or else return the current node.
C++
// C++ program to print intersection of lists#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { int data; Node* next;};// A utility function to return intersection nodeNode* intersectPoint(Node* headA, Node* headB){ stack<Node*> stackA; stack<Node*> stackB; Node* intersectNode = NULL; while (headB != NULL) { stackB.push(headB); headB = headB->next; } while (headA != NULL) { stackA.push(headA); headA = headA->next; } if (!stackA.top()->data == stackB.top()->data) { return NULL; } while (!stackA.empty() && !stackB.empty() && stackA.top()->data == stackB.top()->data) { intersectNode = stackA.top(); stackA.pop(); stackB.pop(); } return intersectNode;}// Driver codeint main(){ /* Create two linked lists 1st Linked list is 3.6.9.15.30 2nd Linked list is 10.15.30 15 30 are elements in the intersection list */ 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; Node* intersect_node = NULL; // Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2); cout << "INTERSECTION POINT: " << intersect_node->data;}// This code is contributed by Tapesh(tapeshdua420) |
Java
// JAVA program to print intersection of listsimport java.util.*;class GFG { /* Link list node */ static class Node { int data; Node next; }; // A utility function to return intersection node static Node intersectPoint(Node headA, Node headB) { Stack<Node> stackA = new Stack<Node>(); Stack<Node> stackB = new Stack<Node>(); Node intersectNode = null; while (headB != null) { stackB.push(headB); headB = headB.next; } while (headA != null) { stackA.push(headA); headA = headA.next; } if (!stackA.peek().equals(stackB.peek())) { return null; } while (!stackA.empty() && !stackB.empty() && stackA.peek().equals(stackB.peek())) { intersectNode = stackA.pop(); stackB.pop(); } return intersectNode; } // Driver code public static void main(String[] args) { /* Create two linked lists 1st Linked list is 3.6.9.15.30 2nd Linked list is 10.15.30 15 30 are elements in the intersection list */ 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; Node intersect_node = null; // Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2); System.out.print("INTERSECTION POINT: " + intersect_node.data); }} |
Python3
# Python program to print intersection of lists# Link list nodeclass Node: def __init__(self, data): self.data = data self.next = None# A utility function to return intersection nodedef intersectPoint(headA, headB): stackA = [] stackB = [] intersectNode = None while headB != None: stackB.append(headB) headB = headB.next while headA != None: stackA.append(headA) headA = headA.next if not stackA[-1].data == stackB[-1].data: return None while stackA and stackB and stackA[-1].data == stackB[-1].data: intersectNode = stackA[-1] stackA.pop() stackB.pop() return intersectNode# Driver codeif __name__ == '__main__': # Create two linked lists # 1st Linked list is 3.6.9.15.30 # 2nd Linked list is 10.15.30 # 15 30 are elements in the intersection list head1 = Node(10) head2 = Node(3) newNode = Node(6) head2.next = newNode newNode = Node(9) head2.next.next = newNode newNode = Node(15) head1.next = newNode head2.next.next.next = newNode newNode = Node(30) head1.next.next = newNode head1.next.next.next = None # Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2) print("INTERSECTION POINT:", intersect_node.data)# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# program to print intersection of listsusing System;using System.Collections.Generic;class GFG { /* Link list node */ class Node { public int data; public Node next; }; // A utility function to return intersection node static Node intersectPoint(Node headA, Node headB) { Stack<Node> stackA = new Stack<Node>(); Stack<Node> stackB = new Stack<Node>(); Node intersectNode = null; while (headB != null) { stackB.Push(headB); headB = headB.next; } while (headA != null) { stackA.Push(headA); headA = headA.next; } if (!stackA.Peek().Equals(stackB.Peek())) { return null; } while (!stackA.Count.Equals(0) && !stackB.Count.Equals(0) && stackA.Peek().Equals(stackB.Peek())) { intersectNode = stackA.Pop(); stackB.Pop(); } return intersectNode; } // Driver code public static void Main(String[] args) { /* Create two linked lists 1st Linked list is 3.6.9.15.30 2nd Linked list is 10.15.30 15 30 are elements in the intersection list */ 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; Node intersect_node = null; // Find the intersection node of two linked lists intersect_node = intersectPoint(head1, head2); Console.WriteLine("INTERSECTION POINT: " + intersect_node.data); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript program to print intersection of lists/* Link list node */class Node { constructor(data) { this.data = data; this.next = null; }}// A utility function to return intersection nodefunction intersectPoint(headA, headB) { let stackA = []; let stackB = []; let intersectNode = null; while (headB != null) { stackB.push(headB); headB = headB.next; } while (headA != null) { stackA.push(headA); headA = headA.next; } if (!stackA[stackA.length - 1].data == stackB[stackB.length - 1].data) { return null; } while (stackA && stackB && stackA[stackA.length - 1].data == stackB[stackB.length - 1].data) { intersectNode = stackA[stackA.length - 1]; stackA.pop(); stackB.pop(); } return intersectNode;}// Driver code/*Create two linked lists1st Linked list is 3.6.9.15.302nd Linked list is 10.15.3015 30 are elements in the intersection list*/var head1 = new Node(10);var head2 = new Node(3);var 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 = null;// Find the intersection node of two linked listsvar intersect_node = intersectPoint(head1, head2);console.log("INTERSECTION POINT:", intersect_node.data);// This code is contributed by Tapesh(tapeshdua420) |
Output
INTERSECTION POINT :15
Time Complexity: O(M + N), where N and M are the length of the two lists.
Auxiliary Space: O(M + N)
Please write comments if you find any bug in the above algorithm or a better way to solve the same problem.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
