- Intersection of Two Linked Lists:题目链接
方法1：(推荐)
基本思想：curA指向A当前节点，curB指向B当前节点，只要A从a1开始遍历，b从b2开始遍历只要curA==curB，则说明找到了公共节点，那么重点就是怎么让b从b2开始，curA遍历A只要curA不为空就继续遍历，如果curA为空，则将B赋值给CurA，同理curB遍历B只要curB不为空就继续遍历，如果curB为空，则将A赋值给curB这样可以使其同步
1 | A: a1 → a2 |
AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13// 时间复杂度O(N) 空间复杂度0(1)
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if (NULL == headA || NULL == headB) {
return NULL;
}
struct ListNode *curA = headA, *curB = headB;
while (curA != curB) {
curA = curA == NULL ? headB : curA->next;
curB = curB == NULL ? headA : curB->next;
}
return curA;
}
方法2：
基本思想;先遍历链表A，计算出A的长度lenA，同理计算lenB，用dist保存| lenA-lenB |，将较长的链表存放在lonHead，lonHead进行dist次lonHead = lonHead->next次操作，此时两个链表已经保持相对位置，开始遍历只要发现存在节点相等则说明有公共节点
AC代码：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// 时间复杂度O(N+M) N：headA的长度 M：headB的长度 空间复杂度0(1)
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if (NULL == headA || NULL == headB) {
return NULL;
}
int lenA = lengthList(headA), lenB = lengthList(headB), dist = 0;
struct ListNode * lonHead = NULL, * shoHead = NULL;
// 确定 headA headB谁长 长多少
if (lenA > lenB) {
lonHead = headA;
shoHead = headB;
dist = lenA - lenB;
} else{
lonHead = headB;
shoHead = headA;
dist = lenB - lenA;
}
// 将较长的链表与较短的统一一下相对位置
while (dist--){
lonHead = lonHead->next;
}
// 只要发现较长链表中有节点和较短链表相等 则说明有公共节点
while (lonHead != NULL) {
if (lonHead == shoHead) {
break;
} else{
lonHead = lonHead->next;
shoHead = shoHead->next;
}
}
return lonHead;
}