Skip to content

Commit 95fac0d

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lcof problem: No.052. Get Intersection Node
1 parent 2257a93 commit 95fac0d

File tree

6 files changed

+104
-142
lines changed

6 files changed

+104
-142
lines changed

‎lcof/面试题52. 两个链表的第一个公共节点/README.md

Lines changed: 56 additions & 73 deletions
Original file line numberDiff line numberDiff line change
@@ -50,9 +50,11 @@
5050

5151
## 解法
5252

53-
先求出两个链表的长度差 `len1-len2`，之后遍历链表，长的链表先走 `len1-len2` 步。
53+
使用两个指针 `cur1`, `cur2` 分别指向两个链表 `headA`, `headB`。
5454

55-
接着两个链表同时走，当出现相同的节点时，说明两个链表在此节点相交，返回此节点，否则返回 `null`。
55+
同时遍历链表，当 `cur1` 到达链表 `headA` 的末尾时，重新定位到链表 `headB` 的头节点；当 `cur2` 到达链表 `headB` 的末尾时，重新定位到链表 `headA` 的头节点。
56+
57+
若两指针相遇，所指向的结点就是第一个公共节点。若没相遇，说明两链表无公共节点，此时两个指针都指向 `null`。
5658

5759
<!-- tabs:start -->
5860

@@ -67,27 +69,11 @@
6769

6870
class Solution:
6971
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
70-
if headA is None or headB is None:
71-
return None
72-
len1 = len2 = 0
73-
p, q = headA, headB
74-
while p:
75-
p = p.next
76-
len1 += 1
77-
while q:
78-
q = q.next
79-
len2 += 1
80-
p, q = headA, headB
81-
if len1 > len2:
82-
p, q = q, p
83-
for _ in range(abs(len1 - len2)):
84-
q = q.next
85-
while p and q:
86-
if p == q:
87-
return p
88-
p = p.next
89-
q = q.next
90-
72+
cur1, cur2 = headA, headB
73+
while cur1 != cur2:
74+
cur1 = headB if cur1 is None else cur1.next
75+
cur2 = headA if cur2 is None else cur2.next
76+
return cur1
9177
```
9278

9379
### **Java**
@@ -106,38 +92,12 @@ class Solution:
10692
*/
10793
public class Solution {
10894
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
109-
if (headA == null || headB == null) {
110-
return null;
111-
}
112-
ListNode p = headA, q = headB;
113-
int len1 = len(p), len2 = len(q);
114-
if (len1 > len2) {
115-
ListNode t = headA;
116-
headA = headB;
117-
headB = t;
95+
ListNode cur1 = headA, cur2 = headB;
96+
while (cur1 != cur2) {
97+
cur1 = cur1 == null ? headB : cur1.next;
98+
cur2 = cur2 == null ? headA : cur2.next;
11899
}
119-
p = headA;
120-
q = headB;
121-
for (int i = 0; i < Math.abs(len1 - len2); ++i) {
122-
q = q.next;
123-
}
124-
while (p != null && q != null) {
125-
if (p == q) {
126-
return p;
127-
}
128-
p = p.next;
129-
q = q.next;
130-
}
131-
return null;
132-
}
133-
134-
private int len(ListNode node) {
135-
int len = 0;
136-
while (node != null) {
137-
node = node.next;
138-
++len;
139-
}
140-
return len;
100+
return cur1;
141101
}
142102
}
143103
```
@@ -158,14 +118,14 @@ public class Solution {
158118
* @param {ListNode} headB
159119
* @return {ListNode}
160120
*/
161-
var getIntersectionNode = function (headA, headB) {
162-
let h1 = headA;
163-
let h2 = headB;
164-
while (h1 !== h2) {
165-
h1 = h1 === null ? headB : h1.next;
166-
h2 = h2 === null ? headA : h2.next;
167-
}
168-
return h2;
121+
var getIntersectionNode = function(headA, headB) {
122+
let cur1 = headA;
123+
let cur2 = headB;
124+
while (cur1 != cur2) {
125+
cur1 = cur1 ? cur1.next : headB;
126+
cur2 = cur2 ? cur2.next : headA;
127+
}
128+
return cur1;
169129
};
170130
```
171131

@@ -180,25 +140,48 @@ var getIntersectionNode = function (headA, headB) {
180140
* ListNode(int x) : val(x), next(NULL) {}
181141
* };
182142
*/
183-
184143
class Solution {
185144
public:
186145
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
187-
ListNode* a = headA;
188-
ListNode* b = headB;
189-
while (a != b) {
190-
/* 这个循环的思路是，a先从listA往后走，如果到最后，就接着从listB走；b正好相反。
191-
如果有交集的话，a和b会在分别进入listB和listA之后的循环中项目
192-
如果没有交集的话，则a和b会同时遍历完listA和listB后，值同时为nullptr */
193-
a = (a == nullptr) ? headB : a->next;
194-
b = (b == nullptr) ? headA : b->next;
146+
ListNode* cur1 = headA;
147+
ListNode* cur2 = headB;
148+
while (cur1 != cur2) {
149+
cur1 = cur1 ? cur1->next : headB;
150+
cur2 = cur2 ? cur2->next : headA;
195151
}
196-
197-
return a;
152+
return cur1;
198153
}
199154
};
200155
```
201156
157+
### **Go**
158+
159+
```go
160+
/**
161+
* Definition for singly-linked list.
162+
* type ListNode struct {
163+
* Val int
164+
* Next *ListNode
165+
* }
166+
*/
167+
func getIntersectionNode(headA, headB *ListNode) *ListNode {
168+
cur1, cur2 := headA, headB
169+
for cur1 != cur2 {
170+
if cur1 == nil {
171+
cur1 = headB
172+
} else {
173+
cur1 = cur1.Next
174+
}
175+
if cur2 == nil {
176+
cur2 = headA
177+
} else {
178+
cur2 = cur2.Next
179+
}
180+
}
181+
return cur1
182+
}
183+
```
184+
202185
### **...**
203186

204187
```

‎lcof/面试题52. 两个链表的第一个公共节点/Solution.cpp

Lines changed: 7 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -6,17 +6,15 @@
66
* ListNode(int x) : val(x), next(NULL) {}
77
* };
88
*/
9-
109
class Solution {
1110
public:
1211
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
13-
ListNode* a = headA;
14-
ListNode* b = headB;
15-
while (a != b) {
16-
a = (a == nullptr) ? headB : a->next;
17-
b = (b == nullptr) ? headA : b->next;
12+
ListNode* cur1 = headA;
13+
ListNode* cur2 = headB;
14+
while (cur1 != cur2) {
15+
cur1 = cur1 ? cur1->next : headB;
16+
cur2 = cur2 ? cur2->next : headA;
1817
}
19-
20-
return a;
18+
return cur1;
2119
}
22-
};
20+
};

‎lcof/面试题52. 两个链表的第一个公共节点/Solution.go

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* type ListNode struct {
4+
* Val int
5+
* Next *ListNode
6+
* }
7+
*/
8+
func getIntersectionNode(headA, headB *ListNode) *ListNode {
9+
cur1, cur2 := headA, headB
10+
for cur1 != cur2 {
11+
if cur1 == nil {
12+
cur1 = headB
13+
} else {
14+
cur1 = cur1.Next
15+
}
16+
if cur2 == nil {
17+
cur2 = headA
18+
} else {
19+
cur2 = cur2.Next
20+
}
21+
}
22+
return cur1
23+
}

‎lcof/面试题52. 两个链表的第一个公共节点/Solution.java

Lines changed: 5 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -11,37 +11,11 @@
1111
*/
1212
public class Solution {
1313
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
14-
if (headA == null || headB == null) {
15-
return null;
14+
ListNode cur1 = headA, cur2 = headB;
15+
while (cur1 != cur2) {
16+
cur1 = cur1 == null ? headB : cur1.next;
17+
cur2 = cur2 == null ? headA : cur2.next;
1618
}
17-
ListNode p = headA, q = headB;
18-
int len1 = len(p), len2 = len(q);
19-
if (len1 > len2) {
20-
ListNode t = headA;
21-
headA = headB;
22-
headB = t;
23-
}
24-
p = headA;
25-
q = headB;
26-
for (int i = 0; i < Math.abs(len1 - len2); ++i) {
27-
q = q.next;
28-
}
29-
while (p != null && q != null) {
30-
if (p == q) {
31-
return p;
32-
}
33-
p = p.next;
34-
q = q.next;
35-
}
36-
return null;
37-
}
38-
39-
private int len(ListNode node) {
40-
int len = 0;
41-
while (node != null) {
42-
node = node.next;
43-
++len;
44-
}
45-
return len;
19+
return cur1;
4620
}
4721
}

‎lcof/面试题52. 两个链表的第一个公共节点/Solution.js

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -11,12 +11,12 @@
1111
* @param {ListNode} headB
1212
* @return {ListNode}
1313
*/
14-
var getIntersectionNode = function (headA, headB) {
15-
let h1 = headA;
16-
let h2 = headB;
17-
while (h1 !== h2) {
18-
h1 = h1 === null ? headB : h1.next;
19-
h2 = h2 === null ? headA : h2.next;
14+
var getIntersectionNode = function(headA, headB) {
15+
let cur1 = headA;
16+
let cur2 = headB;
17+
while (cur1 != cur2) {
18+
cur1 = cur1 ? cur1.next : headB;
19+
cur2 = cur2 ? cur2.next : headA;
2020
}
21-
return h2;
22-
};
21+
return cur1;
22+
};

‎lcof/面试题52. 两个链表的第一个公共节点/Solution.py

Lines changed: 5 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -6,24 +6,8 @@
66

77
class Solution:
88
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
9-
if headA is None or headB is None:
10-
return None
11-
len1 = len2 = 0
12-
p, q = headA, headB
13-
while p:
14-
p = p.next
15-
len1 += 1
16-
while q:
17-
q = q.next
18-
len2 += 1
19-
p, q = headA, headB
20-
if len1 > len2:
21-
p, q = q, p
22-
for _ in range(abs(len1 - len2)):
23-
q = q.next
24-
while p and q:
25-
if p == q:
26-
return p
27-
p = p.next
28-
q = q.next
29-
9+
cur1, cur2 = headA, headB
10+
while cur1 != cur2:
11+
cur1 = headB if cur1 is None else cur1.next
12+
cur2 = headA if cur2 is None else cur2.next
13+
return cur1

0 commit comments

Comments
 (0)