mojinhui33
0%

双指针

发表于 分类于

两个链表的第一个公共节点

力扣Offer52题

时间复杂度O(n+m),空间复杂度O(1)

设l1的不同部分为长度n,l2的不同部分长度为m,俩链表相同部分为t;

则  l1=n+t,l2=m+t;

可知  l1+m=l2+n;

总结：两指针遍历俩个链表，至少第二次会进行匹配。若长度相同，则第一次进行匹配。

1
2
3
4
5
6
7
8
if (headA == null || headB == null) return null;
        ListNode node1 = headA;
        ListNode node2 = headB;
        while (node1 != node2){
            node1 = (node1 == null) ? headB : node1.next;
            node2 = (node2 == null) ? headA : node2.next;
        }
        return node1;

设短的一方l1为甲方，长的那一方l2为乙方

那么，当甲方遍历完到达最后一个点时，乙方还没有遍历完，他们之间的距离就是他们的长度差，为l2 - l1 = m - n，然后甲方再去乙方，继续循环，当甲方走过了他们的长度差，乙方也便利完了，然后乙方就去甲方，这时他们的长度一样