version at: 2022-04-19

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
/**
1. 要求O(n+m) 时间复杂度寻找, n+m是两条链表的长度, 可见m+n是一个确定值
2. 让2个指针a, b分别从2条链表出发, 分别遍历2条链表
    2.1 a 指针走 [a1, a2] -> [c1, c3] -> [b1, b3]
    2.2 b 指针走 [b1, b3] -> [c1, c3] -> [a1, a2]
    可见这两条路径是长度相同的, 他们也会同时到达, 且下一个点就是相交点, 所以a,b指针相交即所求
*/

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }

        return a;
    }
}

version:2020-02-02

/*
1. 找到交点所以要知道第一个被访问两次的点但是要求O（1）的空间并且不能改结构，所以无法记录
2. 剩下的特征就是两条链表长度一定，所以用相同步速遍历链表在相遇处必定为交点
2.1 当 len（a） == lan（b）时直接在c1得到交点
2.2 当 len（a） ！= len（b） 时，当每个链表遍历结束后开始遍历另一条
即a： a->c->b->c1, b: b->c->a->c1 ,因为a，b，c长度一定，步长相等所以必定在c1第一次相遇
2.3 当没有交点时必定在null相遇

3.testcase：有相遇-》 a，b长度相等，a，b长度不等； 无相遇-》 ； null
*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        var a = headA;
        var b = headB;
        while (a != b){
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}