两个链表的第一个公共结点
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
class Solution {
public:
//计算链表长度的函数 fast-template
int ListLenth( ListNode* pHead){
ListNode* p = pHead;
int n = 0;
while(p != NULL){
n++;
p = p->next;
}
return n;
}
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
int p1 = ListLenth(pHead1);
int p2 = ListLenth(pHead2);
//当链表1更长时,链表1指针先走p1-p2步
if(p1 >= p2){
int n = p1 - p2;
for(int i = 0; i < n; i++){
pHead1 = pHead1->next;
}
//两个链表同时移动,直到有公共结点时停下
while((pHead1 != NULL) && (pHead2 != NULL) && (pHead1 != pHead2)){
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
}
//反之,则链表2先行p2-p1步
else{
int n = p2 - p1;
for(int i = 0; i < n; i++){
pHead2 = pHead2->next;
}
//两个链表同时移动,直到有公共结点时停下
while((pHead1 != NULL) && (pHead2 != NULL) && (pHead1 != pHead2)){
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
}
return pHead1;
}
};