How can you find the intersection point of two linked lists?

Arrays Linked Lists Questions Medium



46 Short 80 Medium 67 Long Answer Questions Question Index

How can you find the intersection point of two linked lists?

To find the intersection point of two linked lists, we can use the following approach:

1. Traverse both linked lists and calculate their lengths.
2. Find the difference in lengths between the two lists.
3. Move the pointer of the longer list by the difference in lengths.
4. Now, iterate through both lists simultaneously until we find a common node or reach the end of either list.
5. If a common node is found, it is the intersection point.
6. If we reach the end of either list without finding a common node, it means there is no intersection point.

Here is the implementation in Python:


```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def getIntersectionNode(headA, headB):
# Calculate lengths of both lists
lenA, lenB = 0, 0
currA, currB = headA, headB
while currA:
lenA += 1
currA = currA.next
while currB:
lenB += 1
currB = currB.next

# Move the pointer of the longer list by the difference in lengths
currA, currB = headA, headB
if lenA > lenB:
for _ in range(lenA - lenB):
currA = currA.next
else:
for _ in range(lenB - lenA):
currB = currB.next

# Iterate through both lists simultaneously until a common node is found or end is reached
while currA and currB:
if currA == currB:
return currA
currA = currA.next
currB = currB.next

# No intersection point found
return None
```

This algorithm has a time complexity of O(m + n), where m and n are the lengths of the two linked lists.