## Solution

#### Approach 1: Brute Force

For each node ai in list A, traverse the entire list B and check if any node in list B coincides with ai.

Complexity Analysis

• Time complexity : .

• Space complexity : .

#### Approach 2: Hash Table

Traverse list A and store the address / reference to each node in a hash set. Then check every node bi in list B: if bi appears in the hash set, then bi is the intersection node.

Complexity Analysis

• Time complexity : .

• Space complexity : or .

#### Approach 3: Two Pointers

• Maintain two pointers and initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.
• When reaches the end of a list, then redirect it to the head of B (yes, B, that's right.); similarly when reaches the end of a list, redirect it the head of A.
• If at any point meets , then / is the intersection node.
• To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), would reach the end of the merged list first, because traverses exactly 2 nodes less than does. By redirecting to head A, and to head B, we now ask to travel exactly 2 more nodes than would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.
• If two lists have intersection, then their last nodes must be the same one. So when / reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.

Complexity Analysis

• Time complexity : .

• Space complexity : .