/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
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<
break;
}
count ++;
}
cout<<listNodeVec.size()<<endl;
if(count == 0)
{
//cout<<"ddd"<
return listNodeVec[0];
}else{
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;
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)