双指针解决链表公共节点

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

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=190&&tqId=35197&rp=1&ru=/ta/job-code-high-rd&qru=/ta/job-code-high-rd/question-ranking

假设链表一走到相同节点的距离为a,链表二为b,从相同节点到末尾的距离为c;
我们可以让两个链表走相同的路,若走到相同节点,就返回。
算法核心: a+b+c = b+c+c
就算它们走完都没有相同节点,也不碍事,返回的都是null也是相等的。

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2){
            p1 = (p1 == null ? pHead2 : p1.next);
            p2 = (p2 == null ? pHead1 : p2.next);
        }
        return p1;
    }
全部评论

相关推荐

Richard奇:还得是有鹅选鹅
投递腾讯等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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