Intersection of Two Linked Lists(0160/Easy)

Write a program to find the node at which the intersection of two singly linked lists begins.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

设 A 的长度为 a + c， B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b

= b + c + a。

当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样

地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这

样就能控制访问 A 和 B 两个链表的指针能同时访问到交点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         ListNode A= headA;
        ListNode B= headB;
        while (A!=B) {
            if (A== null)  A = headB;
            else A= A.next;
            if (B==null)  B = headA;
            else B=B.next;
        }
       return A;

    }
}