# [LeetCode][160. Intersection of Two Linked Lists] 2 Approaches: HashSet and Two Pointers with Detailed Explanation

*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.

Traverse the linked list \(\textit{headA}\), and add each node in the linked list \(\textit{headA}\) to the \(\texttt{HashSet}\);

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.

1 | public static ListNode getIntersectionNode_hash(ListNode headA, ListNode headB) { |

## 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}\).

1 | public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { |

## 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. 😉😃💗