160. Intersection of Two Linked Lists
Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 1
Acceptance rate: 44.5%
Problem Breakdown
The problem requires finding the intersection node of two singly linked lists, headA and headB. If there is no intersection, the function should return null. The constraints guarantee that there are no cycles in the linked lists. The goal is to solve this problem with an O(n) time complexity and O(1) space complexity.
Inputs:
- Two singly linked lists,
headAandheadB.
Outputs:
- The node at which the two lists intersect, or
nullif they do not intersect.
Implicit Constraints/Edge Cases:
- The linked lists may have different lengths.
- If there is no intersection, return
null. - The solution should be efficient in terms of both time and space.
Intuition
A brute-force approach would involve checking each node in headA against every node in headB, resulting in a time complexity of O(m * n). This is inefficient for large lists. A better approach involves leveraging the fact that if we traverse both lists, they will eventually meet at the intersection point if one exists. By aligning the lengths of the two lists, we can ensure that when we traverse them simultaneously, we will either find the intersection or reach the end of both lists.
Approach
- Calculate Lengths: Traverse each list to determine its length.
- Align Lengths: Move the pointer of the longer list forward by the difference in lengths so that both pointers are at the same distance from the potential intersection point.
- Traverse Simultaneously: Move both pointers one step at a time until they either meet (at the intersection node) or reach the end of their respective lists.
This approach ensures that we traverse each list at most twice, resulting in an O(n) time complexity and O(1) space complexity.
Complexity Analysis
- Time Complexity:
O(m + n), wheremis the length ofheadAandnis the length ofheadB. We traverse each list once to calculate its length and then traverse them again to find the intersection. - Space Complexity:
O(1), as we only use a constant amount of extra space for pointers.
Solution
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
# Helper function to calculate the length of a linked list
def get_length(node):
length = 0
while node:
length += 1
node = node.next
return length
# Calculate lengths of both lists
lenA, lenB = get_length(headA), get_length(headB)
# Align the pointers by moving the longer list's pointer forward
if lenA > lenB:
for _ in range(lenA - lenB):
headA = headA.next
else:
for _ in range(lenB - lenA):
headB = headB.next
# Traverse both lists simultaneously to find the intersection
while headA and headB:
if headA == headB:
return headA
headA, headB = headA.next, headB.next
# If no intersection is found, return null
return None
Edge Cases Handled
- No Intersection: The function returns
nullif the lists do not intersect. - Different Lengths: The approach handles lists of different lengths by aligning them before traversal.
- Single Node Lists: The solution works correctly even if one or both lists contain only a single node.