Problem: 160. 相交链表
解析
调整到一致的步伐
首先把两个指针调整到与链表结尾相同的距离，然后一起往后遍历，找到第一个相同的指针，就是第一个公共节点
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
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int aLen = 0, bLen = 0;
ListNode *nodeA, *nodeB;
nodeA = headA;
while (nodeA != nullptr) {
++aLen;
nodeA = nodeA->next;
}
nodeA = headA;
nodeB = headB;
while (nodeB != nullptr) {
++bLen;
nodeB = nodeB->next;
}
nodeB = headB;
if (aLen >= bLen) {
for (int i = 0; i < aLen - bLen; ++i) {
nodeA = nodeA->next;
}
while (nodeA != nodeB) {
nodeA = nodeA->next;
nodeB = nodeB->next;
}
return nodeA;
} else {
for (int i = 0; i < bLen - aLen; ++i) {
nodeB = nodeB->next;
}
while (nodeA != nodeB) {
nodeA = nodeA->next;
nodeB = nodeB->next;
}
return nodeA;
}
}
};
|
