leetcode链接：
https://leetcode.cn/problems/intersection-of-two-linked-lists/
方案一
暴力求解，一定可以得到最终结果，但是时间复杂度未n* m ，算法优化方面其是无法接受的
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
| public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempA = headA;
ListNode tempB = headB;
ListNode result = null;
while (tempA != null) {
while (tempB != null) {
if (tempA == tempB) {
result = tempA;
break;
}
tempB = tempB.next;
}
if (result != null) {
break;
}
tempA = tempA.next;
tempB = headB;
}
return result;
}
}
|
Accepted
- 39/39 cases passed (1197 ms)
- Your runtime beats 5.26 % of java submissions
- Your memory usage beats 25.53 % of java submissions (45.2 MB)
分析
时间复杂度：
O( n * m )
空间复杂度：
O( 1 )
方案二—-哈希集合
https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
while (temp != null) {
visited.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (visited.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
作者：LeetCode-Solution
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
较优方案—双指针
https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempA = headA, tempB = headB;
while (tempA != tempB) {
if (tempA == null) {
tempA = headB;
} else {
tempA = tempA.next;
}
if (tempB == null) {
tempB = headA;
} else {
tempB = tempB.next;
}
}
return tempA;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
作者：reals
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
Accepted
- 39/39 cases passed (1 ms)
- Your runtime beats 98.22 % of java submissions
- Your memory usage beats 11.21 % of java submissions (45.4 MB)
分析
时间复杂度：
O( n + m )
空间复杂度：
O( 1 )