首页 > 其他 > 详细

求两个链表的第一个公共节点(建模有趣)

时间:2018-11-14 10:45:08      阅读:151      评论:0      收藏:0      [点我收藏+]

题目描述:

技术分享图片

析:本题如果采用暴力遍历方法的话,最大时间复杂度为O((m + n)* (l + n))

技术分享图片

其实这道题可以建模成一个相遇问题,如上图所示:A和B同时出发,速度均为1,求他们的相遇点p,很明显,当行走路程达到(m + n + l)时,两者路程相同,相遇,代码如下:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
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;
    }
};

 

求两个链表的第一个公共节点(建模有趣)

原文:https://www.cnblogs.com/zf-blog/p/9956602.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!