Intersection of Two Linked Lists
Easy
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
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' Explanation: 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' Explanation: 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 Explanation: 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.
Could you write a solution that runs in O(m + n) time and use only O(1) memory?
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- Can the linked lists contain cycles?
- Are the linked lists guaranteed to be non-empty?
- If the lists intersect, is it possible for them to intersect at multiple points?
- Are the values within the nodes of the linked lists unique, or can they contain duplicates?
- By 'intersect', do you mean they share the exact same node object in memory, or simply have nodes with equal values at some point?
Brute Force Solution
Approach
We want to find where two lists connect, like two roads merging into one. The most straightforward way is to check every possible pair of locations from the two lists to see if they are the same point. This approach is like comparing each item in one list against every item in the other list until we find a match.
Here's how the algorithm would work step-by-step:
- Start with the very first item of the first list.
- Then, go through every single item in the second list and see if any of them is the exact same as the item you picked from the first list.
- If you find a match, you've found the intersection point, and you are done.
- If you don't find a match after checking every item in the second list, move on to the second item in the first list.
- Repeat the process of comparing this second item from the first list with every item in the second list.
- Keep repeating this process of picking an item from the first list and comparing it to every item in the second list until you either find a match or you run out of items in the first list.
Code Implementation
def get_intersection_node_brute_force(head_a, head_b):
current_node_list_a = head_a
# Iterate through each node in the first linked list
while current_node_list_a:
current_node_list_b = head_b
# Compare the current node from the first list
# with every node in the second list
while current_node_list_b:
# Check if the current nodes are the same node
if current_node_list_a == current_node_list_b:
# If the nodes are the same, we've found the intersection
return current_node_list_a
current_node_list_b = current_node_list_b.next
# Move to the next node in the first list
current_node_list_a = current_node_list_a.next
# If there is no intersection, return None
return NoneBig(O) Analysis
Optimal Solution
Approach
The key insight is that if two lists intersect, their tails will be identical. We first figure out how much longer one list is than the other. Then, we advance the pointer of the longer list by the difference in lengths so both pointers are equidistant from the potential intersection point.
Here's how the algorithm would work step-by-step:
- First, walk through each linked list to find out how long each one is.
- Figure out which list is longer and by how much.
- Move the pointer of the longer list forward by the difference in lengths. This way, both pointers will be the same distance from the end of their respective lists.
- Now, move both pointers forward one step at a time, comparing the nodes they point to.
- If the pointers ever point to the exact same node, that's where the lists intersect! Return that node.
- If you reach the end of both lists without finding a matching node, it means they don't intersect at all. Return nothing in this case.
Code Implementation
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def get_intersection_node(head_a, head_b):
list_a_length = 0
list_b_length = 0
current_node_a = head_a
current_node_b = head_b
while current_node_a:
list_a_length += 1
current_node_a = current_node_a.next
while current_node_b:
list_b_length += 1
current_node_b = current_node_b.next
current_node_a = head_a
current_node_b = head_b
# Advance the pointer of the longer list
if list_a_length > list_b_length:
length_difference = list_a_length - list_b_length
for _ in range(length_difference):
current_node_a = current_node_a.next
elif list_b_length > list_a_length:
length_difference = list_b_length - list_a_length
for _ in range(length_difference):
current_node_b = current_node_b.next
# Move both pointers until they meet or reach the end
while current_node_a and current_node_b:
# Comparing the actual node objects, not just values
if current_node_a == current_node_b:
return current_node_a
current_node_a = current_node_a.next
current_node_b = current_node_b.next
return NoneBig(O) Analysis
Edge Cases
| Case | How to Handle |
|---|---|
| Both linked lists are null | Return null immediately as there can be no intersection. |
| One linked list is null, the other is not | Return null immediately as there can be no intersection. |
| Both lists are single nodes and they are the same node | Return that single node as it's the intersection. |
| Both lists are single nodes and they are different nodes | Return null as there is no intersection. |
| The lists intersect at the first node of both lists (same list) | The algorithm should correctly identify the head as the intersection point. |
| The lists do not intersect at all | The algorithm should correctly identify that there is no intersection and return null. |
| One list is significantly longer than the other | The pointer manipulation approach ensures that differing lengths are accounted for by aligning the tails. |
| Lists are very long, approaching memory limits | The solution should perform efficiently without creating excessive copies or auxiliary data structures, minimizing memory usage. |
