@@ -13,12 +13,13 @@ https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
13
13
- 链表
14
14
- 双指针
15
15
16
- ### 哈希法
16
+ ## 解法一: 哈希法
17
17
18
- - 有 A, B 这两条链表, 先遍历其中一个,比如 A 链表, 并将 A 中的所有节点存入哈希表。
19
- - 遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点
18
+ 有 A, B 这两条链表, 先遍历其中一个,比如 A 链表, 并将 A 中的所有节点存入哈希表。
20
19
21
- 伪代码:
20
+ 遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点
21
+
22
+ - 伪代码
22
23
23
24
``` jsx
24
25
data = new Set () // 存放A链表的所有节点的地址
@@ -37,7 +38,10 @@ while B不为空{
37
38
return null // 两条链表没有相交点
38
39
```
39
40
41
+ - 代码支持: JS
42
+
40
43
JS Code:
44
+
41
45
``` js
42
46
let data = new Set ();
43
47
while (A !== null ) {
@@ -56,7 +60,7 @@ return null;
56
60
- 时间复杂度:$O(N)$
57
61
- 空间复杂度:$O(N)$
58
62
59
- ### 解法二:双指针
63
+ ## 解法二:双指针
60
64
61
65
- 例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
62
66
- 当 a 到达链表的尾部时,重定位到链表 B 的头结点
@@ -72,7 +76,7 @@ return null;
72
76
2 . 当 a 指针将链表 1 遍历完后,重定位到链表 B 的头结点,然后继续遍历直至相交点(a 指针遍历的距离为 A + C + B)
73
77
3 . 同理 b 指针遍历的距离为 B + C + A
74
78
75
- 伪代码:
79
+ - 伪代码
76
80
77
81
``` js
78
82
a = headA
@@ -90,7 +94,10 @@ while a,b指针不相等时 {
90
94
return a
91
95
```
92
96
97
+ - 代码支持: JS, Python, Go, PHP
98
+
93
99
JS Code:
100
+
94
101
``` js
95
102
var getIntersectionNode = function (headA , headB ) {
96
103
let a = headA,
@@ -104,6 +111,7 @@ var getIntersectionNode = function (headA, headB) {
104
111
```
105
112
106
113
Python Code:
114
+
107
115
``` py
108
116
class Solution :
109
117
def getIntersectionNode (self , headA : ListNode, headB : ListNode) -> ListNode:
@@ -115,6 +123,7 @@ class Solution:
115
123
```
116
124
117
125
Go Code:
126
+
118
127
``` go
119
128
/* *
120
129
* Definition for singly-linked list.
@@ -145,6 +154,7 @@ func getIntersectionNode(headA, headB *ListNode) *ListNode {
145
154
```
146
155
147
156
PHP Code:
157
+
148
158
``` php
149
159
/**
150
160
* Definition for a singly-linked list.
0 commit comments