160. 相交链表

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

思路： 两个链表相交，就代表两个链表中从某个结点开始出现了重合(注意：这里判断的是结点是否相等而不是结点的值)；由于两个链表的长度未必等长，这给我们遍历带来难度，这可以把两个链表在遍历中临时连接起来，即headA的尾结点为空时 让其指向headB，headB的尾结点为空时，让其指向headA; 因为是临时的不破坏原链表结构

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        if(headA == null || headB == null) return null;
        ListNode currA = headA;
        ListNode currB = headB;
        //只要这两个结点不相同就继续循环 (不相交的两个链表最终相同的是null,这时同样会结束)
        while(currA != currB) {
            currA = (currA==null)?headB:currA.next;
            currB = (currB==null)?headA:currB.next;
        }
       return currA;
    }
}