两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。
链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
链表的操作 可谓是面试一经常的考点。
这题注意几个测试用例：1、空链表；2、两个链表重合；3、两个链表没有公共结点，即不重合；4、其中一个链表表头在另一个链表内；5、一般情况
那么怎么解决这个问题呢。考虑 o—o—o—o—o
–
–
–
o (红色的表示另外一条链表)
如果过说蓝色的为第一个公共点，那么如果从表尾开始往前走就是最后一个公共点，可惜链表一般指的单链表，如果是双链表这题就没有意义了。既然不能从表尾开始，那么只能从表头开始了；
我们可以把上面的情况用栈来实现，先压入栈，然后再弹出，相当于从尾到头！O（m+n）只不过用了赋值空间
但是我们还可以有更好的办法。解法类似于找环的入口结点，这里也是，如果链表一的长度是5、链表二的长度数4，那我就让链表一，，先走一步，再一走，那么他们相遇的点就是第一个公共结点； 如果到表尾还没相遇说明没有公共点。
#include<cstdio>struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};class Solution {public:ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {if(!pHead1) return pHead1;if(!pHead2) return pHead2;int len1=0,len2=0;ListNode *p1,*p2;p1=pHead1;p2=pHead2;while(p1){len1++;p1=p1->next;}while(p2){len2++;p2=p2->next;}p1=pHead1;p2=pHead2;if(len1>len2){while(len1>len2){p1=p1->next;–len1;}}else{while(len1<len2){p2=p2->next;–len2;}}while(p1){if(p1==p2) return p1;p1=p1->next;p2=p2->next;}return p1;}};
版权声明：本文为博主原创文章，未经博主允许不得转载。
在这个阳光明媚的三月，我从我单薄的青春里打马而过，
