How to Solve Intersection of Two Linked Lists

This problem involves finding the intersection of two singly linked lists. Using linked-list pointer manipulation, Hash Tables, or Two Pointers can solve it efficiently. The approach depends on whether memory optimization or runtime speed is prioritized.

Problem Statement

You are given the heads of two singly linked lists, headA and headB. Write a function to determine if they intersect, and if they do, return the node where they intersect. If there is no intersection, return null.

For example, if the two lists intersect at a node, the solution must return that node. Otherwise, it returns null. The intersection is determined based on the node references being identical, not just having equal values. The problem also ensures that there are no cycles in the lists.

Examples

Example 1

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output: Intersected at '8'

The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

• Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output: Intersected at '2'

The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

Output: No intersection

From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so return null.

Constraints

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Solution Approach

Using Hash Tables

One efficient way to solve this problem is by storing all nodes of one linked list in a hash table. Then, iterate through the second linked list, checking if any node already exists in the table. If a match is found, that is the intersection point. The time complexity is O(m + n), where m and n are the lengths of the two lists.

Two Pointer Technique

Using two pointers, traverse both lists. When each pointer reaches the end of a list, redirect it to the beginning of the other list. If the lists intersect, the pointers will meet at the intersection node after traversing the same number of steps. This approach has O(m + n) time complexity with O(1) space complexity.

Simultaneous Traversal with Length Difference Adjustment

First, find the lengths of both linked lists. Then, align the two pointers by advancing the pointer of the longer list by the difference in lengths. After that, traverse both lists simultaneously, checking for the intersection node. This approach also takes O(m + n) time but requires extra space to store list lengths.

Complexity Analysis

The time complexity is O(m + n), where m and n are the lengths of the two linked lists, due to the need to traverse both lists at least once. The space complexity varies: using Hash Tables requires O(m) space, while the Two Pointer method requires O(1) space, making it more space-efficient.

What Interviewers Usually Probe

• Look for a solution using pointer manipulation and minimal space.
• Evaluate if the candidate can optimize the solution for both time and space complexity.
• Check whether the candidate can explain the trade-offs between using hash tables and the two-pointer technique.

Common Pitfalls or Variants

Common pitfalls

• Confusing value equality with reference equality: Make sure to check if the nodes are identical in memory, not just equal in value.
• Failure to handle cases with no intersection correctly: The code should return null when no intersection is found.
• Incorrect space complexity considerations when using Hash Tables: Candidates might underestimate memory usage when opting for hash tables.

Follow-up variants

• What if the two linked lists have a large number of nodes? Consider optimizing the solution further.
• How would you handle the case where one list is much longer than the other? The two-pointer method accounts for this.
• Can the problem be solved with just a single traversal? It depends on the method used—hash tables or two pointers.

How GhostInterview Helps

• GhostInterview provides instant feedback on solving this problem and optimizes solutions for both time and space complexity.
• By walking through different methods like Hash Tables and Two Pointers, GhostInterview helps you identify the best approach for interview scenarios.
• GhostInterview allows you to practice the problem under realistic interview conditions, offering valuable hints on common pitfalls and interview signals.

Topic Pages

• Hash Table
• Linked List
• Two Pointers

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main approach to solving the Intersection of Two Linked Lists problem?

The main approaches involve using Hash Tables or the Two Pointer technique to efficiently find the intersection node, both offering O(m + n) time complexity.

Can this problem be solved in constant space?

Yes, using the Two Pointer technique, the problem can be solved in O(1) space without any extra data structures.

What happens if the two lists don't intersect?

If the two lists don't intersect, the solution will return null, which is the expected behavior when no intersection node exists.

How do the time complexities of the Hash Table and Two Pointer methods compare?

Both methods have O(m + n) time complexity, but the Hash Table method requires additional space, while the Two Pointer method is more space-efficient.

What are common pitfalls when solving the Intersection of Two Linked Lists problem?

Common pitfalls include confusing value equality with reference equality, failing to return null when there's no intersection, and misjudging space complexity when using Hash Tables.