题目描述
输入两个链表,找出它们的第一个公共结点。
思路:这里两个单向链表如果有公共结点肯定是下面这种情况,最后通过公共结点汇合:
1.看到这题我直接想到哈希,直接利用map存储一个链表,第二个链表遍历查找地址即可。
2.链表的叠加,如下图,假设1个链表S1长度a+c,另一个S2为b+c,我们可以把S1链表后面接上S2的头指针,这样,第二次到相交结点应该是a+c+b;
同理,我们先S2后面接S1,这样到达相交结点长度最后也是 b+c+a;
所以直接给个指针遍历到地址相同的地方即可。
方法一:
//1.map
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1 == NULL || pHead2 == NULL)
return NULL;
map<ListNode*,int>p;
while(pHead1 != NULL)
{
p[pHead1] = 1;
pHead1 = pHead1->next;
}
while(pHead2 != NULL)
{
if(p.find(pHead2) != p.end())
return pHead2;
pHead2 = pHead2->next;
}
return NULL;
}
};
方法二:(借助标志位,写的比较糙,可能有改进地方)
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1 == NULL || pHead2 == NULL)
return NULL;
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
int flag1 = 1,flag2 = 1;
while(p1 != NULL)
{
if(p1 == p2)
return p1;
p1 = p1->next;
if(flag1 && p1 == NULL)
{
p1 = pHead2;
flag1 =0;
}
p2 = p2->next;
if(flag2 && p2 == NULL)
{
p2 = pHead1;
flag2 =0;
}
}
return NULL;
}
};