#160

Easy

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Intersection of Two Linked Lists

Given two linked lists, find the node where they intersect or return null if they do not.

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $a$ and $b$ to point to the heads of the two linked lists $\textit{headA}$ and $\textit{headB}$, respectively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

Continue Practicing

#142 linked list cycle ii #141 linked list cycle #148 sort list