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

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.

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)$
• 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}$.

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)$
• 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. 😉😃💗