leetcode.面试题 02.07. 链表相交

题目

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

图示两个链表在节点 c1 开始相交：

思路

假a在链表A上移动,b在链表B上移动，a移动完在B上开始，b移动完再A上开始。最终a移动的距离a + c + x,b移动的距离 b + c + y。可以看到a + c + x = b + c + y,即a + x = b + y ,a移动b距离，b移动a距离a,b指针就会相交，直接返回a,b相交时候a/b指针所指节点的位置。即使a,b没有相交的地方，返回的也是null。

实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         
        //怎么保证a链表上的指针下次指到b链表? 一轮就行了 不用考虑
         ListNode a = headA;
         ListNode b = headB;
         
         while(a != b){
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
         }
        return a;
    }
}