剑指offer 两个链表的第一个公共结点

时间限制：1秒 空间限制：32768K 热度指数：281718

本题知识点： 链表

题目描述

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

题目链接：题目链接

求出LinkedList1的长度为len1，LinktedList2的长度为len2。

如果len1>len2，LinkedList1走len1-len2步；

如果len2>len1，LinkedList2走len2-len1步。

然后LinkedList1和LinkedList2一起走，遇到的第一个相同结点，就是answer。

这样做的前提是两个链表没有环。

原理是，当两个链表有公共结点时，两个链表的末端一定相同。

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode *p1 = pHead1, *p2 = pHead2; int len1 = 0, len2 = 0; //求LinkedList1长度 while(p1 != NULL){ p1 = p1->next; len1 ++ ; } //求LinkedList2长度 while(p2 != NULL){ p2 = p2->next; len2 ++ ; } //计算长度差 int minlen = abs(len1-len2); if(len1 > len2){ while(minlen--){ pHead1 = pHead1->next; } } else { while(minlen--){ pHead2 = pHead2->next; } } //判断链表末端是否相同 while(pHead1 != NULL && pHead2 != NULL){ if(pHead1 == pHead2){ return pHead1; } pHead1 = pHead1->next; pHead2 = pHead2->next; } return NULL; } };

牛油还有更牛逼的做法，把两个链表连接，

LinkedList1 = LinkedList1 + LinkedList2，

LinkedList2 = LinkedList2 + LinkedList1；

判断LinkedList1和LinkedList2末端是否相等。

 

以下是牛油的解释

链接：https://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46?f=discussion 来源：牛客网

有个思路，不需要存储链表的额外空间。也不需要提前知道链表的长度。看下面的链表例子：

0-1-2-3-4-5-null

a-b-4-5-null

代码的ifelse语句，对于某个指针p1来说，其实就是让它跑了连接好的的链表，长度就变成一样了。

如果有公共结点，那么指针一起走到末尾的部分，也就一定会重叠。看看下面指针的路径吧。

p1： 0-1-2-3-4-5-null(此时遇到ifelse)-a-b-4-5-null

p2:  a-b-4-5-null(此时遇到ifelse)0-1-2-3-4-5-null

 

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode *p1 = pHead1, *p2 = pHead2; while(p1 != p2){ p1 = (p1 == NULL ? pHead2 : p1->next); p2 = (p2 == NULL ? pHead1 : p2->next); } return p1; } };