剑指offer-刷题笔记-简单题-JZ52 两个链表的第一个公共结点
版本1-自己写的，不正确，开始认为不断的删除链表1的节点，直到链表2的长度减少，则删除的节点为公共节点。
class Solution {
public:
int GetListLength(ListNode* pHead)
{
int index = 0;
while(pHead)
{
pHead = pHead->next;
index++;
}
return index;
}
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
//pHead1段节点
vector< ListNode* > listNodeVec;
int listLength2 = GetListLength(pHead2);
if(GetListLength(pHead1) <= 1 || GetListLength(pHead2) <= 1)
{
return nullptr;
}
//ListNode* pHead = pHead1;
int count = 0;
while(pHead1)
{
ListNode* pHead = pHead1;
pHead1= pHead1->next;
listNodeVec.push_back(pHead1);
free(pHead);;
if(GetListLength(pHead2) < listLength2)
{
//cout<
//cout<<"ddd"<
return listNodeVec[0];
}
}
};
版本2-双指针，因为两个链表非公共部分长度不一致，所以将两个链表链接为一个链表，这样原来的链表就具有同样的长度，可同时进行遍历，即原来 list1,a+b,list2,c+b,之后list1,c+b+a+b,list2,a+b+c+b，
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode *ta = pHead1, *tb = pHead2;
while (ta != tb) {
ta = ta ? ta->next : pHead2;
tb = tb ? tb->next : pHead1;
}
return ta;
}
};
