剑指offer------两个链表的第一个公共节点
思路:时间复杂度为O(n+a+b)
当p1走了a+n步后到了链表1的尾部,让p1指向链表2,此时p2也走了a+n步,此时p2到链表尾还剩b+n-(a+n)=b-a步;
p2走了b-a步后到了链表2的尾部,让p2指向链表1,此时p1也走了b-a步。
当p2走了a步后到达第一个公共节点,此时p1也走了a步( (b-a)+a=b )刚好也到达第一个公共节点;如果两个链表没有公共节点,则他们就同时到链表尾部,返回NULL。
思路:时间复杂度为O(n+a+b)
当p1走了a+n步后到了链表1的尾部,让p1指向链表2,此时p2也走了a+n步,此时p2到链表尾还剩b+n-(a+n)=b-a步;
p2走了b-a步后到了链表2的尾部,让p2指向链表1,此时p1也走了b-a步。
当p2走了a步后到达第一个公共节点,此时p1也走了a步( (b-a)+a=b )刚好也到达第一个公共节点;如果两个链表没有公共节点,则他们就同时到链表尾部,返回NULL。