两个链表的第一个公共结点

剑指OFFER题16------按牛客网通过率排序

时间：2018.10.25.1931 作者：Waitt

题目

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

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

解答

如果存在共同节点的话，那么从该节点，两个链表之后的元素都是相同的。 第一个公共点之后的next都是一样的，所以必然有公共的尾部。

思路1

如果两个链表均无环，找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走。

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { int len1=0,len2=0; int s; ListNode *p1=pHead1; ListNode *p2=pHead2; while(p1) { len1++; p1=p1->next; } while(p2) { len2++; p2=p2->next; } s=abs(len1-len2); p1=pHead1; p2=pHead2; if(len1>len2) { for(int i=0;i<s;i++) p1=p1->next; } else { for(int i=0;i<s;i++) p2=p2->next; } while(p1) { if(p1==p2) return p1; p1=p1->next; p2=p2->next; } return p1; } };

思路2

假定 List1长度: a+n； List2 长度:b+n, 且 a<b

那么 p1 会先到链表尾部, 这时p2 走到 a+n位置,将p1换成List2头部

接着p2 再走b+n-(n+a) =b-a 步到链表尾部,这时p1也走到List2的b-a位置，还差a步就到可能的第一个公共节点。

将p2 换成 List1头部，p2走a步也到可能的第一个公共节点。如果恰好p1==p2,那么p1就是第一个公共节点。 或者p1和p2一起走n步到达列表尾部，二者没有公共节点，退出循环。 同理a>=b.

时间复杂度O(n+a+b)

/* 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; ListNode *p2=pHead2; while(p1!=p2) { if(p1) p1=p1->next; else p1=pHead2; if(p2) p2=p2->next; else p2=pHead1; } return p1; } };

小知识点

C++变量的地址可使用连字号（&）运算符访问，它表示了在内存中的一个地址。 指针是一个变量，其值为另一个变量的地址，即，内存位置的直接地址。 指针变量声明的一般形式为：

type *var-name;

若指针值一样，则说明指向的地址一样，则其地址所存储的变量为同一变量。 详见：http://www.runoob.com/cplusplus/cpp-pointers.html