思路：双指针
指针A与指针B分别从链表A、B头开始走，走到结尾指向另一个链表头。
当两个指针相遇时，他们指向的节点就是两个链表的第一个公共节点。
原理：小学数学里的相遇问题，二指针在相同时间内走过的距离一样。
假设两个链表的非公共部分长度分别为La，Lb，公共部分长度为C。
相交时A指针走过距离为La+C+Lb，B指针走过距离为Lb+C+La，二者距离相等。
若不相交，则A指针走过距离为La+C+Lb+C，B指针走过距离为Lb+C+La+C，即二指针均走到另一个链表结尾时，
A == null，B == null，A==B，循环结束返回null，不会出现死循环。
代码实现：
时间复杂度O（M+N），空间复杂度O（1）
/** * 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) { ListNode A = headA,B = headB; while(A != B){ if(A != null) A = A.next;//走到结尾 else A = headB; if(B != null) B = B.next; else B = headA; } return A; } }
原文：https://www.cnblogs.com/zccfrancis/p/14403739.html