友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Reference of the node with value = 2 Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: null Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so return null.
Notes:
-
If the two linked lists have no intersection at all, return
null. -
The linked lists must retain their original structure after the function returns.
-
You may assume there are no cycles anywhere in the entire linked structure.
-
Your code should preferably run in O(n) time and use only O(1) memory.
思路分析
没想到竟然可以将两个链表"相加"就可以得出正确结果：两个"相加"，正好两个长度相等，最后部分就是重叠部分，双指针完美搞定！
-
一刷
-
二刷
-
三刷
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
/**
* Runtime: 1 ms, faster than 99.29% of Java online submissions for Intersection of Two Linked Lists.
*
* Memory Usage: 43.3 MB, less than 5.71% of Java online submissions for Intersection of Two Linked Lists.
*
* Copy from: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len![Java solution without knowing the difference in len! - LeetCode Discuss]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-12 11:12
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (Objects.isNull(headA) || Objects.isNull(headB)) {
return null;
}
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
/**
* Runtime: 8 ms, faster than 14.19% of Java online submissions for Intersection of Two Linked Lists.
* <p>
* Memory Usage: 44.2 MB, less than 5.71% of Java online submissions for Intersection of Two Linked Lists.
*/
public ListNode getIntersectionNodeSet(ListNode headA, ListNode headB) {
if (Objects.isNull(headA) || Objects.isNull(headB)) {
return null;
}
Set<ListNode> nodes = new HashSet<>();
ListNode current = headA;
while (Objects.nonNull(current)) {
nodes.add(current);
current = current.next;
}
current = headB;
while (Objects.nonNull(current)) {
if (nodes.contains(current)) {
return current;
}
current = current.next;
}
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 两个链表逻辑拼接
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-02 21:37:57
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode a = headA, b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-02 21:37:57
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while (a != b) {
if (a == null) {
a = headB;
} else {
a = a.next;
}
if (b == null) {
b = headA;
} else {
b = b.next;
}
}
return a;
}