本文为剑指 offer 系列第三十四篇。
主要知识点为链表，找两个链表的第一个公共结点,用个set,非常简单。
输入两个链表，找出它们的第一个公共结点。
解题思路
遍历一个链表，然后将所有节点存到set中，然后依次遍历另一个链表，在set中查看是否有这个节点，如果有，就返回这个节点。
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| /*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
set<ListNode*> mset;
ListNode* p = pHead1;
while(p){
mset.insert(p);
p = p->next;
}
ListNode* q = pHead2;
while(q){
if(mset.count(q)) return q;
q = q->next;
}
return NULL;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！