By Long Luo

This article is the solution 2 Approaches: HashSet and Two Pointers with Detailed Explanation of Problem 160. Intersection of Two Linked Lists.

Here shows 2 Approaches to slove this problem: HashSet and Two Pointers.

# HashSet

We can use $\texttt{HashSet}$ to store linked list nodes.

1. Traverse the linked list $\textit{headA}$, and add each node in the linked list $\textit{headA}$ to the $\texttt{HashSet}$;

2. Traverse the linked list $\textit{headB}$. For each node traversed, check whether the node is in the $\texttt{HashSet}$.

• If the current node is Not in the $\texttt{HashSet}$, continue to traverse the next node;

• If the current node is in the $\texttt{HashSet}$, then all nodes starting from the current node are in the intersection of the two linked lists. Therefore, the first node traversed in the linked list $\textit{headB}$ is the node intersected by the two linked lists.

• If all the nodes in the linked list $\textit{headB}$ are Not in the $\texttt{HashSet}$, the two linked lists do not intersect and $\textit{null}$ is returned.

## Analysis

• Time Complexity: $O(m + n)$
• Space Complexity: $O(m)$

# Two Pointers

If $\textit{headA}$ or $\textit{headB}$ is empty, they cann’t intersect each other.

If both $\textit{headA}$ and $\textit{headB}$ are not null, we can use Two Pointers $\textit{pA}$ and $\textit{pB}$ which point to the head nodes $\textit{headA}$ and $\textit{headB}$.

Then traverse each node of $\textit{headA}$ and $\textit{headB}$ with $\textit{pA}$ and $\textit{pB}$.

• We needs to update the pointers $\textit{pA}$ and $\textit{pB}$ at the same time.

• If the pointer $\textit{pA}$ is not null, move the pointer $\textit{pA}$ to the next node; If the pointer $\textit{pB}$ is not $\textit{null}$, move the pointer $\textit{pB}$ to the next node.

• If the pointer $\textit{pA}$ is null, move the pointer $\textit{pA}$ to the head node of the linked list $\textit{headB}$ ; If the pointer $\textit{pB}$ is null, move the pointer $\textit{pB}$ to the head node of $\textit{headA}$ .

• When the $\textit{pA}$ and $\textit{pB}$ point to the same node or both are null, return the node they point to or $\textit{null}$.

## Analysis

• Time Complexity: $O(m + n)$
• Space Complexity: $O(1)$

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗