题目描述
输入两个链表，找出它们的第一个公共结点。
思路
如果两个链表有公共节点，那么者两个链表组成的形状是Y型的
我们可以考虑处理两个链表的非公共部分，舍弃长链表笔短链表长的部分
然后两个链表同时遍历，就可以遍历到公节点。
当然，暴力枚举也是可以试一下的
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
输入两个链表，找出它们的第一个公共结点。
*/
class Solution {
public:
unsigned int GetListLength(ListNode *pHead) {
int length = 0;
while (pHead != nullptr) {
length++;
pHead = pHead->next;
}
return length;
}
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
// 非法判断
if (pHead1 == nullptr || pHead2 == nullptr) {
return nullptr;
}
// 得到两个链表的长度
unsigned int nLength1 = GetListLength(pHead1);
unsigned int nLength2 = GetListLength(pHead2);
int nLengthDif = nLength1 - nLength2;
// 长短链表交换
ListNode* pListHeadLong = pHead1;
ListNode* pListHeadShort = pHead2;
if(nLength2 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
}
// 先在长链表上走两个链表差值的长度，再同时在两个链表上遍历
for(int i = 0; i < nLengthDif; ++i)
pListHeadLong = pListHeadLong->next;
// 一起移动，直到到达第一个公共的节点
while((pListHeadLong != nullptr) &&
(pListHeadShort != nullptr) &&
(pListHeadLong != pListHeadShort))
{
pListHeadLong = pListHeadLong->next;
pListHeadShort = pListHeadShort->next;
}
// 得到第一个公共结点
ListNode* pFisrtCommonNode = pListHeadLong;
return pFisrtCommonNode;
}
};
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
