Reference: LeetCode EPI 7.4
Difficulty: EasyTwo Pointers

Problem

Write a program to find the node at which the intersection of two singly linked lists begins.

Note:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in $O(n)$ time and use only $O(1)$ memory.

Example: 

1
2
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8

1
2
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null

Analysis

Brute-Force

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  if (headA == null || headB == null) {
    return null;
  }
  ListNode pA = headA;
  while (pA != null) {
    ListNode pB = headB;
    while (pB != null) {
      if (pB == pA) {
        return pA;
      }
      pB = pB.next;
    }
    pA = pA.next;
  }
  return null;
}

Time: $O(mn)$
Space: $O(1)$

Hash Table

Traverse list $A$ and store the address to each node in a hash set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  if (headA == null || headB == null) {
    return null;
  }
  
  Set<ListNode> seen = new HashSet<>();
  ListNode pA = headA;
  while (pA != null) {
    seen.add(pA);
    pA = pA.next;
  }
  
  ListNode pB = headB;
  while (pB != null) {
    if (seen.contains(pB)) return pB;
    pB = pB.next;
  }
  
  return null;
}

Time: $O(m + n)$
Space: $O(m)$ or $O(n)$

Two Pointers

Two pointers pa and pb respectively start from list $A$ and list $B$.

  • If pa reaches the end, it then points to the head of list $B$.
  • If pb reaches the end, it then points to the head of list $A$.

We only change pa and pb in that way once.

  • If they coincide later, return true.
  • If one of them reaches null, return false.
    • Or we can implement without the once logic. See details below.

Two Pointers Illustration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 1
// [] -> []                  // return in the first round
// [] -> []
//
// 2
// [] -> [] -> []            // return in the second round
// [] -> []
//
// 3
// [] -> [] \
//           [] -> []        //  return in the first round
// [] -> [] /
//
// 4
// [] -> [] -> [] \
//                 [] -> []  // return in the second round
//       [] -> [] /

Code:

1
2
3
4
5
6
7
8
9
10
11
12
public 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) ? headB : pA.next;
    pB = (pB == null) ? headA : pB.next;
  }
  return pA;
}

Time: $O(m + n)$
Space: $O(1)$s

Length Difference

Get the length of each list and calculate the difference. According to this difference, one list moves in advance by steps. Then move in tandem and they will reach the intersection node if it exists; otherwise, one of them may reach the end and the program returns null.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public ListNode getIntersectionNode(ListNode l1, ListNode l2) {
  // get the difference in length
  int diff = getLenDiff(l1, l2);

  if (diff >= 0) { // l1 is longer or the same
    while (diff > 0) {
      l1 = l1.next;
      diff -= 1;
    }
  } else { // l2 is longer or the same
    while (diff < 0) {
      l2 = l2.next;
      diff += 1;
    }
  }
  
  while (l1 != null && l2 != null) {
    if (l1 == l2) {
      return l1;   // intersection node exists
    }
    l1 = l1.next;
    l2 = l2.next;
  }
  return null; // no intersection node
}

private int getLenDiff(ListNode l1, ListNode l2) {
  int len1 = 0, len2 = 0;
  while (l1 != null || l2 != null) {
    if (l1 != null) {
      len1 += 1;
      l1 = l1.next;
    }
    if (l2 != null) {
      len2 += 1;
      l2 = l2.next;
    }
  }
  return len1 - len2;
}

Time: $O(m + n)$
Space: $O(1)$