# Intersection of Two Linked Lists

## # Definition for Singly-Linked List

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

1
2
3
4

## # Solution

Let $m$ be the length of list $A$, and $n$ be the length of list $B$.

The brute force solution of squared time complexity is omitted.

### # HashSet

Complexity

time: $O(m + n)$
space: $O(m)$

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
setA = set()
while pA:
pA = pA.next
# return pB is in setA
while pB:
if pB in setA:
return pB
pB = pB.next

1
2
3
4
5
6
7
8
9
10
11
12

### # Two Pointers

Complexity

time: $O(m + n)$
space: $O(1)$

If you switch head, the possible difference between length would be counted. On the second traversal, pA and pB either hit or miss. If they meet, either node can be returned. Otherwise, they will hit at the end in the 2nd iteration, pA == pB == None, and return either one of them is the same: None.

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: