Problem: 160. 相交链表
思路
真正写起来还是1方法好理解
- 去取差值法
可以先遍历链表得到长度,计算长度差,在用a,b指针分别指向长链表和短链表,a先走长度差次,然后就和b一起走,当a == b时,就相遇了
- 连接法
a,b一开始指向两个链表的头,同时开始遍历,短的会先到结尾null处到了之后让他指向另一个的头,继续同时遍历,这时长的也到头了,将他指向另一个链表的头,这时两个需要遍历的长度是一致的,只要有节点,一定会相遇。
pA走过的路径为A链+B链
pB走过的路径为B链+A链
pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
1
2
3
4
5
|
pA:1->2->3->4->5->6->null->9->5->6->null
pB:9->5->6->null->1->2->3->4->5->6->null
|
解题方法
法2:
- 如果pA遍历到结尾
- 指向headB
- 否则
- 指向next
- 如果pB遍历到结尾
- 指向headA
- 否则
- 指向next
复杂度
时间复杂度:
添加时间复杂度, 示例： $O(n)$
空间复杂度:
添加空间复杂度, 示例： $O(n)$
Code
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
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *a = headA,*b = headB;
while(a!=nullptr&&b!=nullptr){
a = a->next;
b = b->next;
}
int diff = 0;
ListNode *longList,*shortList;
if(a==nullptr) {
longList = headB;
shortList = headA;
}else {
swap(a,b);
longList = headA;
shortList = headB;
}
while(b!=nullptr) {
b = b->next;
diff++;
}
while(diff--) longList = longList->next;
while(longList != nullptr && shortList != nullptr && longList != shortList) {
longList = longList->next;
shortList = shortList->next;
}
return longList;
}
};
|
法1:
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int aLength,bLength;
aLength = getLength(headA);
bLength = getLength(headB);
if(aLength<bLength) {
std::swap(aLength,bLength);
std::swap(headA,headB);
}
int differ = aLength - bLength;
ListNode *pA = headA;
ListNode *pB = headB;
while(differ--) {
pA = pA->next;
}
while(pA != pB) {
pA = pA->next;
pB = pB->next;
}
return pA;
}
int getLength(ListNode *node) {
ListNode *cur;
cur = node;
int length = 0;
while(cur != nullptr) {
cur = cur->next;
length++;
}
return length;
}
};
|
法2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while(pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
|