力扣-160.找出两个链表的交点

题目：
leetcode 160.Intersection of Two Linked Lists (Easy)
Write a program to find the node at which the intersection of two singly linked lists begins.
写出程序，找出两个单链表开始的交点。
例如以下示例中 A 和 B 两个链表相交于 c1：

1
2
3
4
5

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

题目大意：
单链表找出第一个交点，没有交点返回null。

解题思路：
本题有个规律：如果将A链长度看作 a + c, B链长度看作 b + c,其中c为尾部公共部分长度，可知a + c + b = b + c + a。
首先遍历两个链表，访问A链表时，当访问到链表尾部时，令它继续从B链表的头部继续开始访问链表；同样，访问B链表时，访问链表尾部时，令它继续从链表A的头部开始访问链表A。这样A的遍历序列就是 a c b c、B的遍历序列就是b c a c，利用上面规律，总可以保证两个链表在遍历时能同时访问到交点，即第二个 c 。
如果不存在交点时，如 len(A) = a + c, len(B) = b + d，则上述过程访问变为A:a、c、b、d; B:b、d、a、c，仍可保证两个链表会同时为null(a+c+b+d = b+d+a+c)，退出循环。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

java:
public ListNode getIntersectionNode(ListNode headA,ListNode headB){
    if(headA == null || headB == null) return null;
    ListNode l1 = headA,l2 = headB;
    //需要两个指针l1,l2分别去遍历headA和headB
    //但是这两个链表的头指针需要被记住
    
    while(l1 != l2){
      l1 = (l1 == null) ? headB : l1.next;
      l2 = (l2 == null) ? headA ; l2.next;
    }
    return l1;
}

python: