给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
面试题 02.07. 链表相交
思路
用两个栈，从后往前的思路，分别存储指向 A，B 链表的指针。因为链表相交，则从相交节点往后的节点都是一致的，因此找到第一个不一致的节点，就是相交节点的前驱；如果其中某个栈空了都没有找到，则返回栈空的链表的指针，该指针指向的即为相交节点
哈希集合，用哈希集合存储链表节点。首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中。如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 nullptr
学习点
unordered_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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
stack<ListNode*> stA;
stack<ListNode*> stB;
ListNode* pA = headA;
ListNode* pB = headB;
while (pA != nullptr)
{
stA.push(pA);
pA = pA->next;
}
while (pB != nullptr)
{
stB.push(pB);
pB = pB->next;
}
bool found = false;
while (!stA.empty() && !stB.empty())
{
pA = stA.top();
stA.pop();
pB = stB.top();
stB.pop();
if ((pA != pB) && (pA->next == pB->next))
{
found = true;
break;
}
}
if (found)
{
return (pA->next);
}
else
{
if (stA.empty())
return pA;
else
return pB;
}
}
};
|
无序集合，建立哈希集合
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
26
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode*> uset;
ListNode *p = headA;
while (p != nullptr)
{
uset.insert(p);
p = p->next;
}
p = headB;
while (p != nullptr)
{
if (uset.count(p))
{
return p;
}
p = p->next;
}
return nullptr;
}
};
|
