Find the Intersection Point of Two Linked Lists

119.1k
0

Given heads of two singly linked lists, find the first common node where both lists intersect and form a Y-shaped structure. From the intersection point onward, both linked lists share the same node sequence by reference.

Return the intersection node. Return null when no intersection exists. Node identity, not node value, determines intersection.

Example 1

Input: listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5], shared node value = 8

Output: 8

Explanation: Both linked lists start sharing the same node sequence from value 8.

Example 2

Input: listA = [1, 2, 3], listB = [4, 5]

Output: null

Explanation: No node reference is common between the two linked lists.

Brute Force Approach

Compare every node of the first linked list with every node of the second linked list. Since intersection depends on the same node reference, not just equal values, a matching reference identifies the first common physical node.

Algorithm

  • Initialize a pointer at the head of the first linked list, as nodes are checked from the beginning to find the first intersection.

  • For each node of the first list, initialize another pointer at the head of the second list, so the entire second list can be compared against the current node.

  • Traverse the second list and compare node references, because equal values do not necessarily represent the same physical node.

  • Return the current node from the first list when both pointers reference the same node, as this is the first intersection encountered from the first list.

  • Move the first-list pointer to its next node when no matching reference is found in the second list.

  • Continue these comparisons until every node of the first list has been checked, then return null when no common node exists.

Dry Run

intersecton brute

intersecton brute

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Create a node with the given data value.
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Find the first common node of the two linked lists
// by comparing every node of the first list with
// every node of the second list.
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
// Traverse the first linked list one node at a time.
ListNode* first = headA;
while (first != nullptr) {
// Start from the beginning of the second list
// for every node of the first list.
ListNode* second = headB;
while (second != nullptr) {
// Intersection depends on node reference,
// not on the stored data value.
if (first == second) {
return first;
}
second = second->next;
}
first = first->next;
}
// No common node exists between the two lists.
return nullptr;
}
};
// Create a linked list from the given values.
ListNode* createList(vector<int>& values) {
if (values.empty()) {
return nullptr;
}
// Create the first node and use it as the head.
ListNode* head = new ListNode(values[0]);
ListNode* tail = head;
// Attach the remaining nodes to the list.
for (int index = 1; index < (int)values.size(); index++) {
tail->next = new ListNode(values[index]);
tail = tail->next;
}
return head;
}
// Connect the end of a list to a shared suffix.
// This creates an actual intersection by reference.
void appendShared(ListNode* head, ListNode* shared) {
ListNode* tail = head;
// Reach the last node of the current list.
while (tail->next != nullptr) {
tail = tail->next;
}
// Connect the last node to the shared list.
tail->next = shared;
}
// Driver code.
int main() {
// Nodes unique to the first list.
vector<int> a = {4, 1};
// Nodes unique to the second list.
vector<int> b = {5, 6, 1};
// Nodes shared by both lists.
vector<int> common = {8, 4, 5};
ListNode* headA = createList(a);
ListNode* headB = createList(b);
ListNode* shared = createList(common);
// Attach the same shared nodes to both lists.
// Therefore, both lists intersect at the first node of 'shared'.
appendShared(headA, shared);
appendShared(headB, shared);
Solution solution;
// Find the first common node.
ListNode* answer = solution.getIntersectionNode(headA, headB);
// Print the data of the intersection node.
// Print -1 if the lists do not intersect.
cout << (answer == nullptr ? -1 : answer->data) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × M), where N is the number of nodes in the first linked list and M is the number of nodes in the second linked list.

Space Complexity: O(1), where 1 represents constant extra space used by traversal pointers.

Better Approach

Store the node references of the first linked list in a hash set. This makes it possible to check whether a node from the second list belongs to the first list in O(1) average time, avoiding repeated comparisons.

Algorithm

  • Initialize an empty hash set for node references, because the identity of the node matters rather than its stored value.

  • Traverse the first linked list and insert every node reference into the hash set, creating a record of all nodes belonging to the first list.

  • Start traversing the second linked list from its head, as each node needs to be checked against the stored references.

  • Check whether the current node reference exists in the hash set, because its presence means both lists share this physical node.

  • Return the current node when the lookup succeeds, as it is the first common node encountered in the second list.

  • Move to the next node when the lookup fails and continue until the second list ends.

  • Return null after the complete second list is processed without finding a shared node.

Dry Run

intersection hash set

intersection hash set

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Create a linked list node with the given data value.
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Find the first common node using a hash set.
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
// Store references of all nodes from the first list,
// so nodes can be checked in constant average time.
unordered_set<ListNode*> visited;
// Traverse the first linked list and store each node reference.
ListNode* first = headA;
while (first != nullptr) {
visited.insert(first);
first = first->next;
}
// Traverse the second list and check whether each node
// reference was already present in the first list.
ListNode* second = headB;
while (second != nullptr) {
// The first node found in the set is the intersection node.
if (visited.find(second) != visited.end()) {
return second;
}
second = second->next;
}
// No common node exists between the two lists.
return nullptr;
}
};
// Create a linked list from the given values.
ListNode* createList(vector<int>& values) {
if (values.empty()) {
return nullptr;
}
// Create the first node and use it as the head.
ListNode* head = new ListNode(values[0]);
ListNode* tail = head;
// Attach the remaining nodes in their given order.
for (int index = 1; index < (int)values.size(); index++) {
tail->next = new ListNode(values[index]);
tail = tail->next;
}
return head;
}
// Connect the end of the list to a shared suffix.
// This creates an actual intersection between the two lists.
void appendShared(ListNode* head, ListNode* shared) {
ListNode* tail = head;
// Move to the last node of the current list.
while (tail->next != nullptr) {
tail = tail->next;
}
// Both lists now point to the same shared nodes.
tail->next = shared;
}
// Driver code.
int main() {
// Nodes unique to the first linked list.
vector<int> a = {4, 1};
// Nodes unique to the second linked list.
vector<int> b = {5, 6, 1};
// Nodes shared by both linked lists.
vector<int> common = {8, 4, 5};
ListNode* headA = createList(a);
ListNode* headB = createList(b);
ListNode* shared = createList(common);
// Attach the same nodes to both lists to create an intersection.
appendShared(headA, shared);
appendShared(headB, shared);
Solution solution;
// Find the first common node.
ListNode* answer = solution.getIntersectionNode(headA, headB);
// Print the intersection value, or -1 if no intersection exists.
cout << (answer == nullptr ? -1 : answer->data) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), where N is the number of nodes in the first linked list and M is the number of nodes in the second linked list.

Space Complexity: O(N), where N is the number of nodes in the first linked list whose node references are stored in the hash set.

Optimal Approach

Two pointers can automatically balance the different lengths of the two linked lists without calculating their lengths. Each pointer traverses its own list first and then continues through the other list after reaching the end.

Because both pointers eventually cover the same total distance, any shared suffix causes them to meet at the first common node. If the lists do not intersect, both pointers reach null after covering the same distance.

Algorithm

  • Initialize first at headA and second at headB, so each pointer begins with its respective linked list.

  • Continue traversal while first and second refer to different nodes, because equality indicates that the intersection point has been reached.

  • Move first to first->next, and redirect it to headB when it reaches null, allowing it to cover both list lengths.

  • Move second to second->next, and redirect it to headA when it reaches null, giving both pointers the same total traversal distance.

  • Continue the two traversals until both pointers reference the same node.

  • Return first, which is either the first intersection node or null when the lists do not intersect.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Create a linked list node with the given data value.
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Find the first common node using pointer switching.
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
// Start one pointer at each linked list.
ListNode* first = headA;
ListNode* second = headB;
// Continue until both pointers refer to the same node.
while (first != second) {
// Move first forward; after reaching the end of list A,
// continue from the beginning of list B.
first = (first == nullptr) ? headB : first->next;
// Move second forward; after reaching the end of list B,
// continue from the beginning of list A.
second = (second == nullptr) ? headA : second->next;
}
// Both pointers either meet at the intersection node
// or become nullptr when no intersection exists.
return first;
}
};
// Create a linked list from the given values.
ListNode* createList(vector<int>& values) {
if (values.empty()) {
return nullptr;
}
// Create the first node and use it as the head.
ListNode* head = new ListNode(values[0]);
ListNode* tail = head;
// Attach the remaining nodes in their given order.
for (int index = 1; index < (int)values.size(); index++) {
tail->next = new ListNode(values[index]);
tail = tail->next;
}
return head;
}
// Connect the end of the list to a shared suffix.
// This creates an actual intersection between the two lists.
void appendShared(ListNode* head, ListNode* shared) {
ListNode* tail = head;
// Move to the last node of the current list.
while (tail->next != nullptr) {
tail = tail->next;
}
// Both lists now point to the same shared nodes.
tail->next = shared;
}
// Driver code.
int main() {
// Nodes unique to the first linked list.
vector<int> a = {4, 1};
// Nodes unique to the second linked list.
vector<int> b = {5, 6, 1};
// Nodes shared by both linked lists.
vector<int> common = {8, 4, 5};
ListNode* headA = createList(a);
ListNode* headB = createList(b);
ListNode* shared = createList(common);
// Attach the same nodes to both lists to create an intersection.
appendShared(headA, shared);
appendShared(headB, shared);
Solution solution;
// Find the first common node.
ListNode* answer = solution.getIntersectionNode(headA, headB);
// Print the intersection value, or -1 if no intersection exists.
cout << (answer == nullptr ? -1 : answer->data) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), where N is the number of nodes in the first linked list and M is the number of nodes in the second linked list.
Space Complexity: O(1), where 1 represents constant extra space used by the two traversal pointers.

FAQs

Q1. Does equal node value mean intersection?
No. Intersection requires the same node reference, not equal stored value.

Q2. Can pointer switching handle no intersection?
Yes. Both pointers become null after covering equal total distance, so null is returned.

Q3. Why does pointer switching work with different list lengths?
Switching heads makes both pointers travel N + M nodes, removing the initial length difference automatically.

Q4. Can hashing solve the problem in linear time?
Yes. Hashing gives linear time, but requires extra memory for stored node references.

Q5. How does the optimal approach handle lists with no intersection?
If the lists do not intersect, both pointers eventually reach null after traversing both lists, so they meet at null and the algorithm returns null.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.8k
Linked List

Merge Two Sorted Linked Lists

Input: list1 = [1, 2, 4], list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] Explanation: Values from both sorted lists are arranged in non-decreasing order. Input: list1 = [], list2 = [0] Output: [0] Ex...

114.6k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0