题目描述
输入两个链表，找出它们的第一个公共结点。
思路：用一个unordered_set记录已访问的链表的地址，第一个重复出现的地址，即为第一个公共结点
代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
//ListNode* res;
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
unordered_set<ListNode*> s;
while(p1 != NULL || p2 != NULL) {
if(p1) {
if(s.find(p1) != s.end()) {
return p1;
}
s.insert(p1);
p1 = p1->next;
}
if(p2) {
if(s.find(p2) != s.end()) {
return p2;
}
s.insert(p2);
p2 = p2->next;
}
}
return NULL;
}
};思路二：
先求出两个链表的总长度，让较长链表的头指针移动两链表长度差，此时再让两个头指针同时往后移动，则一定会同时到达第一个公共结点，每次移动后判断两个头指针是否相同即可，若相同，则此时的结点即为第一个公共结点。
该方法相比于第一种，节省了额外的空间开销，两种方法的时间复杂度均是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) {
int len1 = getLen(pHead1);
int len2 = getLen(pHead2);
int tmp = len1 - len2;
if(len1 > len2) {
while(tmp--) {
pHead1 = pHead1->next;
}
} else {
tmp = -tmp;
while(tmp--) {
pHead2 = pHead2->next;
}
}
while(pHead1 != NULL && pHead2 != NULL && pHead1 != pHead2) {
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
return pHead1;
}
int getLen(ListNode* p) {
int len = 0;
while(p) {
++len;
p = p->next;
}
return len;
}
};