剑指offer 两个链表的第一个公共结点
- 题目描述
输入两个链表，找出它们的第一个公共结点。
- 解法分析
从题目入手可以想到两种方法。
-
蛮力法 —— 在第一链表上顺序遍历每个结点，每遍历到一个结点的时候，在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和第一个链表上的结点一样，说明两个链表在这个结点上重合，于是就找到了它们的公共结点。如果第一个链表的长度为m，第二个链表的长度为n，显然该方法的时间复杂度是
O(mn)。 -
首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。这种方法的最大时间复杂度是
O(m+n)。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
ListNode* ret = NULL;
if (pHead1 == NULL || pHead2 == NULL)
return ret;
int size1 = 0, size2 = 0;
ListNode*p1 = pHead1, *p2 = pHead2;
while (p1 != NULL){
size1++;
p1 = p1->next;
}
while (p2 != NULL){
size2++;
p2 = p2->next;
}
int sub = (size1 > size2) ? (size1 - size2) : (size2 - size1);
p1 = pHead1;
p2 = pHead2;
if (size1 > size2){
for (int i = 0; i < sub; ++i)
p1 = p1->next;
}
else{
for (int i = 0; i < sub; ++i)
p2 = p2->next;
}
for (int i = 0; i<(size1>size2) ? size2 : size1; i++){
if (p1 == NULL || p2 == NULL)
break;
else if (p1->val == p2->val){
ret = p1;
return ret;
}
else{
p1 = p1->next;
p2 = p2->next;
}
}
return ret;
}
};