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.

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