IntersectionOfTwoLinkedLists160

fluency03 · fluency03 · commit 1493d6a600db · 2018-03-07T23:38:40.000+01:00
diff --git a/src/IntersectionOfTwoLinkedLists160.java b/src/IntersectionOfTwoLinkedLists160.java
@@ -68,6 +68,13 @@ public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 
     /**
      * https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!
+     *
+     * You can prove that: say A length = a + c, B length = b + c, after
+     * switching pointer, pointer A will move another b + c steps, pointer B
+     * will move a + c more steps, since a + c + b + c = b + c + a + c, it
+     * does not matter what value c is. Pointer A and B must meet after
+     * a + c + b (b + c + a) steps. If c == 0, they meet at NULL.
+     *
      */
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         //boundary check
