第一个公共节点,遍历到最后节点后再从另一个开始

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

http://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46

第一个公共节点,遍历到最后节点后再从另一个开始。

证明:L1特有的长度为m,L2特有的部分为n,相同长度为t。
则 L1=m+t,L2=n+t;
所以L1+n=L2+m;
所以,至少第二次会匹配!

    /**
     * 输入两个链表,找出它们的第一个公共结点。
     * @param pHead1 链表1
     * @param pHead2 链表2
     * @return  第一个公共结点
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode cur1=pHead1,cur2=pHead2;
        while (cur1!=cur2){
            cur1= cur1==null?pHead2:cur1.next;
            cur2=cur2==null?pHead1:cur2.next;
        }
        return cur1;

    }

先求长度差,然后同步开始。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 15:58
投个小米提前批试试水,先投一个岗位看看形势,不行就再沉淀一下投第二个岗位,莫辜负
Java抽象带篮子:我嘞个骚刚,已经开始研发6g了吗
投递小米集团等公司7个岗位
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务