首页 > 其他 > 详细

两个链表第一个公共点

时间:2017-08-19 12:34:32      阅读:237      评论:0      收藏:0      [点我收藏+]

题目描述

输入两个链表,找出它们的第一个公共结点。
 
思路:用两个指针扫描”两个链表“,最终两个指针到达 null 或者到达公共结点。
 
代码所基于的想法是,将两个链表L1和L2进行拼接,得到L1+L2和L2+L1两个拼接结果。这两个拼接后的链表长度是一致的,那么逐个判断即可。
 
/*
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;
    }
};

 

长度相同有公共结点,第一次就遍历到;没有公共结点,走到尾部NULL相遇,返回NULL
长度不同有公共结点,第一遍差值就出来了,第二遍一起到公共结点;没有公共,一起到结尾NULL。

 

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p=pHead1;
        while(p!=NULL){
            ListNode* q=pHead2;
            while(q!=NULL){
                if(p==q){
                    return p;
                }
                q=q->next;
            }
            p=p->next;
        }
        return p;
    }
};

  

两个链表第一个公共点

原文:http://www.cnblogs.com/dd2hm/p/7395844.html

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