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