【剑指offer】面试题37:两个链表的第一个公共结点

时间:2024-01-20 19:15:39

题目:

输入两个链表,找出它们的第一个公共结点。

思路:

由链表的定义知是单链表。对于单链表,如果两个链表有公共结点,则两个链表必然是像Y型相交。则先计算出各个链表的长度,让长链表的头指针先走多出来的几步,再同时让两个链表的指针移动,则判断两个指针是否相等即可。

代码:

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
if(pHead1==NULL || pHead2==NULL) return NULL; int len1=GetListLength(pHead1);
int len2=GetListLength(pHead2);
int diff=len1-len2; ListNode* head1=pHead1;
ListNode* head2=pHead2;
if(diff>)
{
head1=GoNStep(pHead1,diff);
}
else
head2=GoNStep(pHead2,-diff); while(head1!=NULL)
{
if(head1==head2) return head1;
head1=head1->next;
head2=head2->next;
} return NULL;
}
private:
ListNode* GoNStep(ListNode *pHead, int n)
{
for(int i=;i<n;++i)
if(pHead) pHead=pHead->next;
return pHead;
} int GetListLength(ListNode *pHead)
{
int len=;
while(pHead!=NULL)
{
len++;
pHead=pHead->next;
}
return len;
}
};