题目链接
英文链接：https://leetcode.com/problems/intersection-of-two-linked-lists/
中文链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
题目详述
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：
1 | A: a1 → a2 |
在节点 c1 开始相交。
注意：
- 如果两个链表没有交点，返回
null. - 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class LeetCode_00160 {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA;
ListNode pB = headB;
int lenA = 0;
int lenB = 0;
while (pA != null) {
++lenA;
pA = pA.next;
}
while (pB != null) {
++lenB;
pB = pB.next;
}
pA = headA;
pB = headB;
if (lenA > lenB) {
int diff = lenA - lenB;
while (diff-- != 0) {
pA = pA.next;
}
} else {
int diff = lenB - lenA;
while (diff-- != 0) {
pB = pB.next;
}
}
while (pA != pB) {
pA = pA.next;
pB = pB.next;
}
return pA;
}
}
脑洞解法：
在第一次迭代结束时，将指针指向另一个链表的头部。
在第二次迭代时，两个指针要么相遇于相交结点，要么最后都变为 null。
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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class LeetCode_00160 {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA;
ListNode pB = headB;
// 在第二次迭代时，两个指针要么相遇于相交结点，要么最后都变为 null
while (pA != pB) {
// 在第一次迭代结束时，将指针指向另一个链表的头部
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}