160. Intersection of Two Linked Lists

• 160. Intersection of Two Linked Lists
  • 1.1. Description
  • 1.2. Intuition
  • 1.3. Pitfall
  • 1.4. Solution
    • 1.4.1. Visit Set
    • 1.4.2. Cross Visit
    • 1.4.3. Floyd Cycle Detection Algorithm

1.1. Description

Here

1.2. Intuition

这道题目有三种方法

1. Visit Set
2. Cross Visit
3. Floyd Cycle Detection Algorithm

1.3. Pitfall

1.4. Solution

1.4.1. Visit Set

记录headA的visited过的点，看B能否visit到

Solution 1

1.4.2. Cross Visit

用两个a, b，分别指向headA, headB，同时move，如果任意一个先走到了null，那么a指向headB, 而a指向headB, 那么，

1. 两者有相交点，则走过的路成均为x1 + x2 + x3, 则在相交点相遇
2. 如果无有相交点，那么，最终相遇在null

Solution 2

1.4.3. Floyd Cycle Detection Algorithm

很简单的思想，找到headA的tail，那么将headA的tail指向headB, 那么就apply Floyd Cycle Detection Algorithm

Solution 3