160. 相交链表

名字是乱打的

发布于 2021-12-23 19:02:41

3230

发布于 2021-12-23 19:02:41

文章被收录于专栏：软件工程

思路：

可以直接看图，两个指针分别从A，B开始走，走到头后走对方的路，那么两者第一次相等的时候要么是有公共结点然后相较于共同结点上，要么没有相遇点最后都为null

这是为啥？因为我们让两个指针走到头后交换线路继续走，其实两者到相遇的时候走的路是一样长的，比如题目中给的相交图

从a出发到相交走的路为 a1,a2,c1,c2,c3,b1,b2,b3,c1
从b出发到相交走的路为b1,b2,b3 ,c1,c2,c3,a1,a2,c1

代码：

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null){
            return null;
        }

        ListNode startA=headA,startB=headB;
        while (startA!=startB){
            startA=startA==null?headB:startA.next;
            startB=startB==null?headA:startB.next;
        }
        return startA;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/11/2 下，如有侵权请联系 cloudcommunity@tencent.com 删除

null