Find the intersection point of Y LL
Linked-List
FAQs (Medium)
Medium
- This problem, commonly known as the "Linked List Intersection" problem, serves as a fundamental concept in various real-world scenarios in the software industry
- For instance, Git, a widely used version control system, utilizes this concept to identify the "merge base" of two branches - the point where the branches diverged
- Finding this merge base is necessary for Git to efficiently and accurately merge the changes from two branches
- To find the merge base, Git internally represents the commits as a linked list, with each node pointing to its parent commit(s), and essentially solves the Linked List Intersection problem
Given the heads of two linked lists A and B, containing positive integers. Find the node at which the two linked lists intersect. If they do intersect, return the node at which the intersection begins, otherwise return null.
The Linked List will not contain any cycles. The linked lists must retain their original structure, given as per the input, after the function returns.
Note: for custom input, the following parameters are required(your program is not provided with these parameters):
- intersectVal - The value of the node where the intersection occurs. This is -1 if there is no intersected node.
- skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node(-1 if no intersection).
- skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node(-1 if no intersection).
- listA - The first linked list.
- listB - The second linked list.
Examples:
Input: listA: intersectVal = 4, skipA = 3, skipB = 2, head -> 1 -> 2 -> 3 -> 4 -> 5, listB: head -> 7 -> 8 -> 4 -> 5
Output(value at returned node is displayed): 4
Explanation: The two lists have nodes with values 4 and 5 as their tails.
Input: listA: intersectVal = -1, skipA = -1, skipB = -1, head -> 1 -> 2 -> 3, listB: head -> 8 -> 9
Output(value at returned node is displayed): null
Explanation: The two lists do not intersect.
Input: listA: intersectVal = 4, skipA = 0, skipB = 0, head -> 4 -> 5 -> 6, listB: head -> 4 -> 5 -> 6
Constraints
- m == number of nodes in listA.
- n == number of nodes in listB.
- 1 <= m, n <= 5 * 104
- 1 <= ListNode.val <= 104
- 0 <= skipA < m
- 0 <= skipB < n
- intersectVal, skipA, skipB is -1 if listA and listB do not intersect.
- intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.
Hints
- Pointer A starts at headA, and Pointer B starts at headB. When Pointer A reaches the end of list A, move it to headB. When Pointer B reaches the end of list B, move it to headA.
- If the lists intersect, the pointers will meet at the intersection. If they don’t, both will reach NULL at the same time.
Company Tags
Pinterest
PayPal
ARM
Bain & Company
Western Digital
Texas Instruments
Bloomberg
Walmart
Unity Technologies
Morgan Stanley
OYO Rooms
Riot Games
Splunk
Bungie
MongoDB
Optum
Alibaba
Intel
HCL Technologies
Rakuten
Cloudflare
Dropbox
Airbnb
Wayfair
Roche
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition
To determine the intersection of two linked lists, traverse each list to identify the common node by checking if the nodes match. If a match is found, it indicates the intersection point; otherwise, there is no intersection.Approach
Intersection between two linked lists means they share a common node.
What should be the common attribute for two linked lists?
The common attribute isn't just the node's value, but the node itself. Therefore, we need to identify the exact node that appears in both lists.
Process
- Select one of the linked lists to compare against the other. In this approach, we use the second list.
- Iterate through the nodes of the second list.
- For each node in the second list, check if it is present in the first list by iterating through the first list.
- If a node from the second list is found in the first list, it indicates the first intersection node.
- If no matching node is found after iterating through both lists, it means there is no intersection, and we return null.
Dry Run
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119
#include <iostream>
using namespace std;
//Definition of singly linked list:
struct ListNode
{
int val;
ListNode *next;
ListNode()
{
val = 0;
next = NULL;
}
ListNode(int data1)
{
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1)
{
val = data1;
next = next1;
}
};
class Solution {
public:
//Function to find the intersection node of two linked lists
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// Traverse the second list
while (headB != NULL) {
//For each node in the second list,
//Traverse the first list
ListNode *temp = headA;
while (temp != NULL) {
//If the current node
//Of the first list is the
//Same as the current node of
//The second list
if (temp == headB)
//Intersection node
return headB;
//Move to the next node
//In the first list
temp = temp->next;
}
// Move to the next node
//In the second list
headB = headB->next;
}
//No intersection found
return NULL;
}
};
// Utility function to insert a node at the end of the linked list
void insertNode(ListNode* &head, int val) {
// Create a new node with the given value
ListNode* newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head == NULL) {
head = newNode;
return;
}
// Otherwise, traverse to the end of the list
ListNode* temp = head;
while (temp->next != NULL)
temp = temp->next;
// Insert the new node at the end of the list
temp->next = newNode;
}
// Utility function to print the linked list
void printList(ListNode* head) {
// Traverse the list
while (head->next != NULL) {
// Print the value of each node followed by an arrow
cout << head->val << "->";
head = head->next;
}
// Print the value of the last node
cout << head->val << endl;
}
int main() {
// Creation of the first list
ListNode* head1 = NULL;
insertNode(head1, 1);
insertNode(head1, 3);
insertNode(head1, 1);
insertNode(head1, 2);
insertNode(head1, 4);
// Create an intersection
ListNode* intersection = head1->next->next->next;
// Creation of the second list
ListNode* head2 = NULL;
insertNode(head2, 3);
head2->next = intersection;
// Printing the lists
cout << "List1: ";
printList(head1);
cout << "List2: ";
printList(head2);
// Checking if an intersection is present
Solution sol;
ListNode* answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode == NULL)
cout << "No intersection\n";
else
cout << "The intersection point is " << answerNode->val << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116
import java.util.*;
//Definition of singly linked list:
class ListNode {
int val;
ListNode next;
// Constructor with no parameters
ListNode() {
val = 0;
next = null;
}
// Constructor with one parameter
ListNode(int data1) {
val = data1;
next = null;
}
// Constructor with two parameters
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
// Function to find the intersection node of two linked lists
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// Traverse the second list
while (headB != null) {
// For each node in the second list,
// Traverse the first list
ListNode temp = headA;
while (temp != null) {
// If the current node
// Of the first list is the
// Same as the current node of
// The second list
if (temp == headB)
// Intersection node
return headB;
// Move to the next node
// In the first list
temp = temp.next;
}
// Move to the next node
// In the second list
headB = headB.next;
}
// No intersection found
return null;
}
}
class Main {
public static void insertNode(ListNode head, int val) {
// Create a new node with the given value
ListNode newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head == null) {
head = newNode;
return;
}
// Otherwise, traverse to the end of the list
ListNode temp = head;
while (temp.next != null)
temp = temp.next;
// Insert the new node at the end of the list
temp.next = newNode;
}
// Utility function to print the linked list
public static void printList(ListNode head) {
// Traverse the list
while (head.next != null) {
// Print the value of each node followed by an arrow
System.out.print(head.val + "->");
head = head.next;
}
// Print the value of the last node
System.out.println(head.val);
}
public static void main(String[] args) {
// Creation of the first list
ListNode head1 = new ListNode();
insertNode(head1, 1);
insertNode(head1, 3);
insertNode(head1, 1);
insertNode(head1, 2);
insertNode(head1, 4);
// Create an intersection
ListNode intersection = head1.next.next.next;
// Creation of the second list
ListNode head2 = new ListNode();
insertNode(head2, 3);
head2.next = intersection;
// Printing the lists
System.out.print("List1: ");
printList(head1);
System.out.print("List2: ");
printList(head2);
// Checking if an intersection is present
Solution sol = new Solution();
ListNode answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode == null)
System.out.println("No intersection");
else
System.out.println("The intersection point is " + answerNode.val);
}
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
# Definition of singly linked list:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to find the intersection node of two linked lists
def getIntersectionNode(self, headA, headB):
# Traverse the second list
while headB:
# For each node in the second list,
# traverse the first list
temp = headA
while temp:
# If the current node
# of the first list is the
# same as the current node of
# the second list
if temp == headB:
# Intersection node
return headB
# Move to the next node
# in the first list
temp = temp.next
# Move to the next node
# in the second list
headB = headB.next
# No intersection found
return None
# Utility function to insert a node at the end of the linked list
def insertNode(self, head, val):
# Create a new node with the given value
newNode = ListNode(val)
# If the list is empty, set the new node as the head
if not head:
head = newNode
return
# Otherwise, traverse to the end of the list
temp = head
while temp.next:
temp = temp.next
# Insert the new node at the end of the list
temp.next = newNode
# Utility function to print the linked list
def printList(self, head):
# Traverse the list
while head.next:
# Print the value of each node followed by an arrow
print(head.val, end="->")
head = head.next
# Print the value of the last node
print(head.val)
if __name__ == "__main__":
solution = Solution()
# Creation of the first list
head1 = ListNode()
solution.insertNode(head1, 1)
solution.insertNode(head1, 3)
solution.insertNode(head1, 1)
solution.insertNode(head1, 2)
solution.insertNode(head1, 4)
# Create an intersection
intersection = head1.next.next.next
# Creation of the second list
head2 = ListNode()
solution.insertNode(head2, 3)
head2.next = intersection
# Printing the lists
print("List1: ", end="")
solution.printList(head1)
print("List2: ", end="")
solution.printList(head2)
# Checking if an intersection is present
answerNode = solution.getIntersectionNode(head1, head2)
if answerNode is None:
print("No intersection")
else:
print("The intersection point is", answerNode.val)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
/*
Definition of singly linked list:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
*/
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to find the intersection node of two linked lists
getIntersectionNode(headA, headB) {
// Traverse the second list
while (headB !== null) {
// For each node in the second list,
// traverse the first list
let temp = headA;
while (temp !== null) {
// If the current node
// of the first list is the
// same as the current node of
// the second list
if (temp === headB)
// Intersection node
return headB;
// Move to the next node
// in the first list
temp = temp.next;
}
// Move to the next node
// in the second list
headB = headB.next;
}
// No intersection found
return null;
}
// Utility function to insert a node at the end of the linked list
insertNode(head, val) {
// Create a new node with the given value
const newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head === null) {
head = newNode;
return;
}
// Otherwise, traverse to the end of the list
let temp = head;
while (temp.next !== null)
temp = temp.next;
// Insert the new node at the end of the list
temp.next = newNode;
}
// Utility function to print the linked list
printList(head) {
// Traverse the list
while (head.next !== null) {
// Print the value of each node followed by an arrow
process.stdout.write(head.val + "->");
head = head.next;
}
// Print the value of the last node
console.log(head.val);
}
}
// Main function
(function main() {
const solution = new Solution();
// Creation of the first list
let head1 = new ListNode();
solution.insertNode(head1, 1);
solution.insertNode(head1, 3);
solution.insertNode(head1, 1);
solution.insertNode(head1, 2);
solution.insertNode(head1, 4);
// Create an intersection
const intersection = head1.next.next.next;
// Creation of the second list
let head2 = new ListNode();
solution.insertNode(head2, 3);
head2.next = intersection;
// Printing the lists
process.stdout.write("List1: ");
solution.printList(head1);
process.stdout.write("List2: ");
solution.printList(head2);
// Checking if an intersection is present
const answerNode = solution.getIntersectionNode(head1, head2);
if (answerNode === null)
console.log("No intersection");
else
console.log("The intersection point is " + answerNode.val);
})();
Complexity Analysis
Time Complexity: O(Mx N), where 'M' is the number of nodes in list A and 'N' is the number of nodes in list B. This is because, for each node in list B, we iterate through the entire list A to check if there is an intersection. In the worst-case scenario, if there is no intersection, this results in a nested loop structure where each node in list B is compared with every node in list A, leading to O(MxN) operations. Space Complexity: O(1) This is because no additional data structures are used that scale with the size of the input. We only use a few pointers to traverse the lists, and these require a constant amount of space regardless of the size of the input lists.Intuition
To find where two linked lists intersect, we can use a hash set to remember all the nodes from the first list. Then, as we go through the second list, we check if any node is already in the hash set. The first node that is found in the set is where the lists intersect.Approach
To enhance the time complexity of the brute-force method, we can utilize hashing, which provides an efficient way to search in constant time, O(1). The steps are as follows:
Hashing List 1 Nodes Traverse through the first linked list and hash the addresses of its nodes. This allows us to store each node's address in a hash set, providing a quick way to reference these nodes later.
Searching in List 2 Traverse through the second linked list and check if any node's address is already present in the hash set. If a node from the second list is found in the hash set, it means that this node is the intersection point, and we return it. This efficiently identifies the intersection without the need for nested iterations.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
#include <iostream>
#include <unordered_set>
using namespace std;
// Definition of singly linked list
struct ListNode {
int val;
ListNode *next;
ListNode() {
val = 0;
next = NULL;
}
ListNode(int data1) {
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1) {
val = data1;
next = next1;
}
};
class Solution {
public:
// Function to find the intersection node of two linked lists
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// Create a hash set to store the nodes
//Of the first list
unordered_set<ListNode*> nodes_set;
//Traverse the first linked list
//And add all its nodes to the set
while (headA != NULL) {
nodes_set.insert(headA);
headA = headA->next;
}
//Traverse the second linked list
//And check for intersection
while (headB != NULL) {
// If a node from the second list is found in the set,
// It means there is an intersection
if (nodes_set.find(headB) != nodes_set.end()) {
return headB;
}
headB = headB->next;
}
// No intersection found, return NULL
return NULL;
}
};
// Utility function to insert a node at the end of the linked list
void insertNode(ListNode* &head, int val) {
// Create a new node with the given value
ListNode* newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head == NULL) {
head = newNode;
return;
}
// Otherwise, traverse to the end of the list
ListNode* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
// Insert the new node at the end of the list
temp->next = newNode;
}
// Utility function to print the linked list
void printList(ListNode* head) {
// Traverse the list
while (head->next != NULL) {
// Print the value of each node followed by an arrow
cout << head->val << "->";
head = head->next;
}
// Print the value of the last node
cout << head->val << endl;
}
int main() {
// Creation of the first list
ListNode* head1 = NULL;
insertNode(head1, 1);
insertNode(head1, 3);
insertNode(head1, 1);
insertNode(head1, 2);
insertNode(head1, 4);
// Create an intersection
ListNode* intersection = head1->next->next->next;
// Creation of the second list
ListNode* head2 = NULL;
insertNode(head2, 3);
head2->next = intersection;
// Printing the lists
cout << "List1: ";
printList(head1);
cout << "List2: ";
printList(head2);
// Checking if an intersection is present
Solution sol;
ListNode* answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode == NULL) {
cout << "No intersection\n";
} else {
cout << "The intersection point is " << answerNode->val << endl;
}
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119
import java.util.HashSet;
// Definition of singly linked list
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
// Function to find the intersection node of two linked lists
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// Create a hash set to store the nodes
// Of the first list
HashSet<ListNode> nodes_set = new HashSet<>();
// Traverse the first linked list
// And add all its nodes to the set
while (headA != null) {
nodes_set.add(headA);
headA = headA.next;
}
// Traverse the second linked list
// And check for intersection
while (headB != null) {
// If a node from the second list is found in the set,
// It means there is an intersection
if (nodes_set.contains(headB)) {
return headB;
}
headB = headB.next;
}
// No intersection found, return null
return null;
}
}
// Utility function to insert a node at the end of the linked list
void insertNode(ListNode head, int val) {
// Create a new node with the given value
ListNode newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head == null) {
head = newNode;
return;
}
// Otherwise, traverse to the end of the list
ListNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
// Insert the new node at the end of the list
temp.next = newNode;
}
// Utility function to print the linked list
void printList(ListNode head) {
// Traverse the list
while (head.next != null) {
// Print the value of each node followed by an arrow
System.out.print(head.val + "->");
head = head.next;
}
// Print the value of the last node
System.out.println(head.val);
}
public static void main(String[] args) {
// Creation of the first list
ListNode head1 = new ListNode();
insertNode(head1, 1);
insertNode(head1, 3);
insertNode(head1, 1);
insertNode(head1, 2);
insertNode(head1, 4);
// Create an intersection
ListNode intersection = head1.next.next.next;
// Creation of the second list
ListNode head2 = new ListNode();
insertNode(head2, 3);
head2.next = intersection;
// Printing the lists
System.out.print("List1: ");
printList(head1);
System.out.print("List2: ");
printList(head2);
// Checking if an intersection is present
Solution sol = new Solution();
ListNode answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode == null) {
System.out.println("No intersection");
} else {
System.out.println("The intersection point is " + answerNode.val);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091
# Definition of singly linked list
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to find the intersection node of two linked lists
def getIntersectionNode(self, headA, headB):
# Create a hash set to store the nodes
# Of the first list
nodes_set = set()
# Traverse the first linked list
# And add all its nodes to the set
while headA is not None:
nodes_set.add(headA)
headA = headA.next
# Traverse the second linked list
# And check for intersection
while headB is not None:
# If a node from the second list is found in the set,
# It means there is an intersection
if headB in nodes_set:
return headB
headB = headB.next
# No intersection found, return None
return None
# Utility function to insert a node at the end of the linked list
def insertNode(head, val):
# Create a new node with the given value
newNode = ListNode(val)
# If the list is empty, set the new node as the head
if head is None:
head = newNode
return head
# Otherwise, traverse to the end of the list
temp = head
while temp.next is not None:
temp = temp.next
# Insert the new node at the end of the list
temp.next = newNode
return head
# Utility function to print the linked list
def printList(head):
# Traverse the list
while head.next is not None:
# Print the value of each node followed by an arrow
print(head.val, end="->")
head = head.next
# Print the value of the last node
print(head.val)
if __name__ == "__main__":
# Creation of the first list
head1 = ListNode()
head1 = insertNode(head1, 1)
head1 = insertNode(head1, 3)
head1 = insertNode(head1, 1)
head1 = insertNode(head1, 2)
head1 = insertNode(head1, 4)
# Create an intersection
intersection = head1.next.next.next
# Creation of the second list
head2 = ListNode()
head2 = insertNode(head2, 3)
head2.next = intersection
# Printing the lists
print("List1: ", end="")
printList(head1)
print("List2: ", end="")
printList(head2)
# Checking if an intersection is present
sol = Solution()
answerNode = sol.getIntersectionNode(head1, head2)
if answerNode is None:
print("No intersection")
else:
print("The intersection point is", answerNode.val)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
// Definition of singly linked list
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to find the intersection node of two linked lists
getIntersectionNode(headA, headB) {
// Create a hash set to store the nodes
// Of the first list
let nodesSet = new Set();
// Traverse the first linked list
// And add all its nodes to the set
while (headA !== null) {
nodesSet.add(headA);
headA = headA.next;
}
// Traverse the second linked list
// And check for intersection
while (headB !== null) {
// If a node from the second list is found in the set,
// It means there is an intersection
if (nodesSet.has(headB)) {
return headB;
}
headB = headB.next;
}
// No intersection found, return null
return null;
}
}
// Utility function to insert a node at the end of the linked list
function insertNode(head, val) {
// Create a new node with the given value
let newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head === null) {
head = newNode;
return head;
}
// Otherwise, traverse to the end of the list
let temp = head;
while (temp.next !== null) {
temp = temp.next;
}
// Insert the new node at the end of the list
temp.next = newNode;
return head;
}
// Utility function to print the linked list
function printList(head) {
// Traverse the list
while (head.next !== null) {
// Print the value of each node followed by an arrow
process.stdout.write(head.val + "->");
head = head.next;
}
// Print the value of the last node
console.log(head.val);
}
// Creation of the first list
let head1 = new ListNode();
head1 = insertNode(head1, 1);
head1 = insertNode(head1, 3);
head1 = insertNode(head1, 1);
head1 = insertNode(head1, 2);
head1 = insertNode(head1, 4);
// Create an intersection
let intersection = head1.next.next.next;
// Creation of the second list
let head2 = new ListNode();
head2 = insertNode(head2, 3);
head2.next = intersection;
// Printing the lists
console.log("List1: ");
printList(head1);
console.log("List2: ");
printList(head2);
// Checking if an intersection is present
let sol = new Solution();
let answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode === null) {
console.log("No intersection");
} else {
console.log("The intersection point is " + answerNode.val);
}
Complexity Analysis
Time Complexity: O(N+M) The reason for this time complexity is that we first iterate through all nodes in the first list, which takes O(N) time. After that, we iterate through all nodes in the second list, which takes O(m) time. Therefore, the total time complexity is O(N+M). Space Complexity: O(N) The reason for this space complexity is that we use an unordered_set to store the addresses of all nodes in the first list. The space required for this set depends on the number of nodes in the first list, which is O(N).Intuition
To find the intersection of two linked lists, we use the difference in their lengths to align their starting points and then traverse both lists simultaneously until we find the intersection node.
Approach
To optimize the search for the intersection node, we align the starting points of the two linked lists based on their lengths. Here's the process:
- Calculate the lengths of both linked lists.
- Determine the positive difference between these lengths.
- Advance the pointer of the longer list by this difference, thereby aligning both lists to the same remaining length.
- Traverse both lists simultaneously from these aligned points. The first node where the pointers meet is the intersection node.
Dry Run
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
#include <iostream>
using namespace std;
// Definition of singly linked list
struct ListNode {
int val;
ListNode *next;
ListNode() {
val = 0;
next = NULL;
}
ListNode(int data1) {
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1) {
val = data1;
next = next1;
}
};
class Solution {
public:
// Function to find the intersection node of two linked lists
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//Initialize two pointers,
//d1 and d2
//To the heads of the two lists
ListNode *d1 = headA;
ListNode *d2 = headB;
//Traverse both lists until the pointers meet
while (d1 != d2) {
//Move pointer d1 to the head
//Of the second list if it reaches
//The end of the first list
d1 = d1 == NULL ? headB : d1->next;
//Move pointer d2 to the head
//Of the first list if it reaches
//The end of the second list
d2 = d2 == NULL ? headA : d2->next;
}
//Return the intersection node
return d1;
}
};
// Utility function to insert a node at the end of the linked list
void insertNode(ListNode* &head, int val) {
// Create a new node with the given value
ListNode* newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head == NULL) {
head = newNode;
return;
}
// Otherwise, traverse to the end of the list
ListNode* temp = head;
while (temp->next != NULL) temp = temp->next;
// Insert the new node at the end of the list
temp->next = newNode;
}
// Utility function to print the linked list
void printList(ListNode* head) {
// Traverse the list
while (head->next != NULL) {
// Print the value of each node followed by an arrow
cout << head->val << "->";
head = head->next;
}
// Print the value of the last node
cout << head->val << endl;
}
int main() {
// Creation of the first list
ListNode* head1 = NULL;
insertNode(head1, 1);
insertNode(head1, 3);
insertNode(head1, 1);
insertNode(head1, 2);
insertNode(head1, 4);
// Create an intersection
ListNode* intersection = head1->next->next->next;
// Creation of the second list
ListNode* head2 = NULL;
insertNode(head2, 3);
head2->next = intersection;
// Printing the lists
cout << "List1: ";
printList(head1);
cout << "List2: ";
printList(head2);
// Checking if an intersection is present
Solution sol;
ListNode* answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode == NULL)
cout << "No intersection\n";
else
cout << "The intersection point is " << answerNode->val << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
// Function to find the intersection node of two linked lists
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// Initialize two pointers, d1 and d2
// To the heads of the two lists
ListNode d1 = headA;
ListNode d2 = headB;
// Traverse both lists until the pointers meet
while (d1 != d2) {
// Move pointer d1 to the head
// Of the second list if it reaches
// The end of the first list
d1 = (d1 == null) ? headB : d1.next;
// Move pointer d2 to the head
// Of the first list if it reaches
// The end of the second list
d2 = (d2 == null) ? headA : d2.next;
}
// Return the intersection node
return d1;
}
}
// Utility function to insert a node at the end of the linked list
void insertNode(ListNode head, int val) {
// Create a new node with the given value
ListNode newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head == null) {
head = newNode;
return;
}
// Otherwise, traverse to the end of the list
ListNode temp = head;
while (temp.next != null) temp = temp.next;
// Insert the new node at the end of the list
temp.next = newNode;
}
// Utility function to print the linked list
void printList(ListNode head) {
// Traverse the list
while (head.next != null) {
// Print the value of each node followed by an arrow
System.out.print(head.val + "->");
head = head.next;
}
// Print the value of the last node
System.out.println(head.val);
}
public class Main {
public static void main(String[] args) {
// Creation of the first list
ListNode head1 = null;
insertNode(head1, 1);
insertNode(head1, 3);
insertNode(head1, 1);
insertNode(head1, 2);
insertNode(head1, 4);
// Create an intersection
ListNode intersection = head1.next.next.next;
// Creation of the second list
ListNode head2 = null;
insertNode(head2, 3);
head2.next = intersection;
// Printing the lists
System.out.print("List1: ");
printList(head1);
System.out.print("List2: ");
printList(head2);
// Checking if an intersection is present
Solution sol = new Solution();
ListNode answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode == null)
System.out.println("No intersection");
else
System.out.println("The intersection point is " + answerNode.val);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
# Definition of singly linked list
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to find the intersection node of two linked lists
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# Initialize two pointers, d1 and d2
# To the heads of the two lists
d1, d2 = headA, headB
# Traverse both lists until the pointers meet
while d1 != d2:
# Move pointer d1 to the head
# Of the second list if it reaches
# The end of the first list
d1 = d1.next if d1 else headB
# Move pointer d2 to the head
# Of the first list if it reaches
# The end of the second list
d2 = d2.next if d2 else headA
# Return the intersection node
return d1
# Utility function to insert a node at the end of the linked list
def insertNode(head, val):
# Create a new node with the given value
newNode = ListNode(val)
# If the list is empty, set the new node as the head
if not head:
return newNode
# Otherwise, traverse to the end of the list
temp = head
while temp.next:
temp = temp.next
# Insert the new node at the end of the list
temp.next = newNode
return head
# Utility function to print the linked list
def printList(head):
# Traverse the list
while head.next:
# Print the value of each node followed by an arrow
print(f"{head.val}->", end="")
head = head.next
# Print the value of the last node
print(head.val)
if __name__ == "__main__":
# Creation of the first list
head1 = None
head1 = insertNode(head1, 1)
head1 = insertNode(head1, 3)
head1 = insertNode(head1, 1)
head1 = insertNode(head1, 2)
head1 = insertNode(head1, 4)
# Create an intersection
intersection = head1.next.next.next
# Creation of the second list
head2 = None
head2 = insertNode(head2, 3)
head2.next = intersection
# Printing the lists
print("List1: ", end="")
printList(head1)
print("List2: ", end="")
printList(head2)
# Checking if an intersection is present
sol = Solution()
answerNode = sol.getIntersectionNode(head1, head2)
if not answerNode:
print("No intersection")
else:
print(f"The intersection point is {answerNode.val}")
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
// Definition of singly linked list
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to find the intersection node of two linked lists
getIntersectionNode(headA, headB) {
// Initialize two pointers, d1 and d2
// To the heads of the two lists
let d1 = headA;
let d2 = headB;
// Traverse both lists until the pointers meet
while (d1 !== d2) {
// Move pointer d1 to the head
// Of the second list if it reaches
// The end of the first list
d1 = d1 === null ? headB : d1.next;
// Move pointer d2 to the head
// Of the first list if it reaches
// The end of the second list
d2 = d2 === null ? headA : d2.next;
}
// Return the intersection node
return d1;
}
}
// Utility function to insert a node at the end of the linked list
function insertNode(head, val) {
// Create a new node with the given value
const newNode = new ListNode(val);
// If the list is empty, set the new node as the head
if (head === null) {
return newNode;
}
// Otherwise, traverse to the end of the list
let temp = head;
while (temp.next !== null) temp = temp.next;
// Insert the new node at the end of the list
temp.next = newNode;
return head;
}
// Utility function to print the linked list
function printList(head) {
// Traverse the list
while (head.next !== null) {
// Print the value of each node followed by an arrow
process.stdout.write(`${head.val}->`);
head = head.next;
}
// Print the value of the last node
console.log(head.val);
}
function main() {
// Creation of the first list
let head1 = null;
head1 = insertNode(head1, 1);
head1 = insertNode(head1, 3);
head1 = insertNode(head1, 1);
head1 = insertNode(head1, 2);
head1 = insertNode(head1, 4);
// Create an intersection
const intersection = head1.next.next.next;
// Creation of the second list
let head2 = null;
head2 = insertNode(head2, 3);
head2.next = intersection;
// Printing the lists
process.stdout.write("List1: ");
printList(head1);
process.stdout.write("List2: ");
printList(head2);
// Checking if an intersection is present
const sol = new Solution();
const answerNode = sol.getIntersectionNode(head1, head2);
if (answerNode === null)
console.log("No intersection");
else
console.log(`The intersection point is ${answerNode.val}`);
}
main();
Complexity Analysis
Time Complexity: O(2 x max(length of list1, length of list2)) This is because the algorithm traverses each linked list entirely, ensuring that both pointers traverse the entire length of both lists. The maximum number of steps required is twice the length of the longer list, accounting for the difference in their lengths. Space Complexity: O(1) The algorithm uses only a fixed amount of extra space, as it relies solely on pointer manipulation within the existing lists. No additional data structures are required, making the space complexity constant.Frequently Occurring Doubts
Q: Why does switching pointers ensure they meet at the intersection?
A: By switching at the end, both pointers traverse the same total distance. This guarantees that they meet at the intersection node if one exists.
Q: Can this approach be used if the lists have cycles?
A: No, since we assume lists do not contain cycles. For cycles, Floyd’s Cycle Detection (Tortoise and Hare Algorithm) is required.
Interview Followup Questions
Q: What if we could modify the lists?
A: We could append one list to the other, making intersection detection simpler.
Q: How can this be extended to detect multiple intersections?
A: The problem assumes one intersection, but multiple intersections require extra tracking.
Notes
Code
✅ Testcase
Input: {'nums1': '[1, 2, 3, 4, 5]', 'nums2': '[7, 8, 4, 5]', 'skipA': '3', 'skipB': '2', 'intersecVal': '4'}
Expected:
4
4
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums1': '[1, 2, 3]', 'nums2': '[8, 9]', 'skipA': '-1', 'skipB': '-1', 'intersecVal': '-1'}
Expected:
null
null
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums1': '[4, 5, 6]', 'nums2': '[4, 5, 6]', 'skipA': '0', 'skipB': '0', 'intersecVal': '4'}
Expected:
4
4
Actual: -
Time: -
sec
Status: Waiting