[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 HashSet\texttt{HashSet} to store linked list nodes.

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

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

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

    • If the current node is in the HashSet\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 headB\textit{headB} is the node intersected by the two linked lists.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static ListNode getIntersectionNode_hash(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}

Set<ListNode> seen = new HashSet<>();
while (headA != null) {
seen.add(headA);
headA = headA.next;
}

while (headB != null) {
if (seen.contains(headB)) {
return headB;
}

headB = headB.next;
}

return null;
}

Analysis

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

Two Pointers

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}

ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = pA != null ? pA.next : headB;
pB = pB != null ? pB.next : headA;
}

return pA;
}

Analysis

  • Time Complexity: O(m+n)O(m + n)
  • Space Complexity: O(1)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. 😉😃💗