Skip to content

Commit 1a3b884

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lcof problem: No.22
1 parent e8a28ab commit 1a3b884

File tree

6 files changed

+107
-95
lines changed

6 files changed

+107
-95
lines changed

‎lcof/面试题22. 链表中倒数第k个节点/README.md

Lines changed: 69 additions & 61 deletions
Original file line numberDiff line numberDiff line change
@@ -17,9 +17,13 @@
1717

1818
## 解法
1919

20-
定义快慢指针 `slow`、`fast`，初始指向 `head`。
20+
**方法一：快慢指针**
2121

22-
`fast` 先向前走 `k` 步，接着 `slow`、`fast` 同时向前走，当 `fast` 指向 `null` 时，`slow` 指向的节点即为链表的倒数第 `k` 个节点。
22+
我们可以定义快慢指针 `fast` 和 `slow`，初始时均指向 `head`。
23+
24+
然后快指针 `fast` 先向前走 $k$ 步，然后快慢指针同时向前走，直到快指针走到链表尾部，此时慢指针指向的节点就是倒数第 $k$ 个节点。
25+
26+
时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为链表长度。
2327

2428
<!-- tabs:start -->
2529

@@ -39,8 +43,7 @@ class Solution:
3943
for _ in range(k):
4044
fast = fast.next
4145
while fast:
42-
slow = slow.next
43-
fast = fast.next
46+
slow, fast = slow.next, fast.next
4447
return slow
4548
```
4649

@@ -70,33 +73,76 @@ class Solution {
7073
}
7174
```
7275

76+
### **C++**
77+
78+
```cpp
79+
/**
80+
* Definition for singly-linked list.
81+
* struct ListNode {
82+
* int val;
83+
* ListNode *next;
84+
* ListNode(int x) : val(x), next(NULL) {}
85+
* };
86+
*/
87+
class Solution {
88+
public:
89+
ListNode* getKthFromEnd(ListNode* head, int k) {
90+
ListNode *slow = head, *fast = head;
91+
while (k--) {
92+
fast = fast->next;
93+
}
94+
while (fast) {
95+
slow = slow->next;
96+
fast = fast->next;
97+
}
98+
return slow;
99+
}
100+
};
101+
```
102+
103+
### **Go**
104+
105+
```go
106+
/**
107+
* Definition for singly-linked list.
108+
* type ListNode struct {
109+
* Val int
110+
* Next *ListNode
111+
* }
112+
*/
113+
func getKthFromEnd(head *ListNode, k int) *ListNode {
114+
slow, fast := head, head
115+
for ; k > 0; k-- {
116+
fast = fast.Next
117+
}
118+
for fast != nil {
119+
slow, fast = slow.Next, fast.Next
120+
}
121+
return slow
122+
}
123+
```
124+
73125
### **JavaScript**
74126

75127
```js
128+
/**
129+
* Definition for singly-linked list.
130+
* function ListNode(val) {
131+
* this.val = val;
132+
* this.next = null;
133+
* }
134+
*/
76135
/**
77136
* @param {ListNode} head
78137
* @param {number} k
79138
* @return {ListNode}
80139
*/
81140
var getKthFromEnd = function (head, k) {
82-
// 递归
83-
// let cnt = 1
84-
// function func(node) {
85-
// if(!node || !node.next) return node
86-
// let newNode = func(node.next)
87-
// if(cnt === k) return newNode
88-
// else cnt++
89-
// return node
90-
// }
91-
// return func(head)
92-
93-
// 快慢指针
94-
let slow = head;
95141
let fast = head;
96-
while (k) {
142+
while (k--) {
97143
fast = fast.next;
98-
k--;
99144
}
145+
let slow = head;
100146
while (fast) {
101147
slow = slow.next;
102148
fast = fast.next;
@@ -105,44 +151,6 @@ var getKthFromEnd = function (head, k) {
105151
};
106152
```
107153

108-
### **Go**
109-
110-
```go
111-
func getKthFromEnd(head *ListNode, k int) *ListNode {
112-
tmp := head
113-
for tmp != nil && k > 0{
114-
tmp = tmp.Next
115-
k--
116-
}
117-
slow := head
118-
fast := tmp
119-
for fast != nil {
120-
fast = fast.Next
121-
slow = slow.Next
122-
}
123-
return slow
124-
}
125-
```
126-
127-
### **C++**
128-
129-
```cpp
130-
class Solution {
131-
public:
132-
ListNode* getKthFromEnd(ListNode* head, int k) {
133-
ListNode *slow = head, *fast = head;
134-
while (k--) {
135-
fast = fast->next;
136-
}
137-
while (fast) {
138-
slow = slow->next;
139-
fast = fast->next;
140-
}
141-
return slow;
142-
}
143-
};
144-
```
145-
146154
### **Rust**
147155

148156
```rust
@@ -192,12 +200,12 @@ impl Solution {
192200
public class Solution {
193201
public ListNode GetKthFromEnd(ListNode head, int k) {
194202
ListNode fast = head, slow = head;
203+
while (k-- > 0) {
204+
fast = fast.next;
205+
}
195206
while (fast != null) {
207+
slow = slow.next;
196208
fast = fast.next;
197-
k -= 1;
198-
if (k < 0) {
199-
slow = slow.next;
200-
}
201209
}
202210
return slow;
203211
}

‎lcof/面试题22. 链表中倒数第k个节点/Solution.cpp

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,11 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* struct ListNode {
4+
* int val;
5+
* ListNode *next;
6+
* ListNode(int x) : val(x), next(NULL) {}
7+
* };
8+
*/
19
class Solution {
210
public:
311
ListNode* getKthFromEnd(ListNode* head, int k) {
@@ -11,4 +19,4 @@ class Solution {
1119
}
1220
return slow;
1321
}
14-
};
22+
};

‎lcof/面试题22. 链表中倒数第k个节点/Solution.cs

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -9,12 +9,12 @@
99
public class Solution {
1010
public ListNode GetKthFromEnd(ListNode head, int k) {
1111
ListNode fast = head, slow = head;
12+
while (k-- > 0) {
13+
fast = fast.next;
14+
}
1215
while (fast != null) {
16+
slow = slow.next;
1317
fast = fast.next;
14-
k -= 1;
15-
if (k < 0) {
16-
slow = slow.next;
17-
}
1818
}
1919
return slow;
2020
}

‎lcof/面试题22. 链表中倒数第k个节点/Solution.go

Lines changed: 15 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,17 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* type ListNode struct {
4+
* Val int
5+
* Next *ListNode
6+
* }
7+
*/
18
func getKthFromEnd(head *ListNode, k int) *ListNode {
2-
tmp := head
3-
for tmp != nil && k > 0{
4-
tmp = tmp.Next
5-
k--
6-
}
7-
slow := head
8-
fast := tmp
9-
for fast != nil {
10-
fast = fast.Next
11-
slow = slow.Next
12-
}
13-
return slow
9+
slow, fast := head, head
10+
for ; k > 0; k-- {
11+
fast = fast.Next
12+
}
13+
for fast != nil {
14+
slow, fast = slow.Next, fast.Next
15+
}
16+
return slow
1417
}

‎lcof/面试题22. 链表中倒数第k个节点/Solution.js

Lines changed: 9 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,21 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val) {
4+
* this.val = val;
5+
* this.next = null;
6+
* }
7+
*/
18
/**
29
* @param {ListNode} head
310
* @param {number} k
411
* @return {ListNode}
512
*/
613
var getKthFromEnd = function (head, k) {
7-
// 递归
8-
// let cnt = 1
9-
// function func(node) {
10-
// if(!node || !node.next) return node
11-
// let newNode = func(node.next)
12-
// if(cnt === k) return newNode
13-
// else cnt++
14-
// return node
15-
// }
16-
// return func(head)
17-
18-
// 快慢指针
19-
let slow = head;
2014
let fast = head;
21-
while (k) {
15+
while (k--) {
2216
fast = fast.next;
23-
k--;
2417
}
18+
let slow = head;
2519
while (fast) {
2620
slow = slow.next;
2721
fast = fast.next;

‎lcof/面试题22. 链表中倒数第k个节点/Solution.py

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,5 @@ def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
1111
for _ in range(k):
1212
fast = fast.next
1313
while fast:
14-
slow = slow.next
15-
fast = fast.next
14+
slow, fast = slow.next, fast.next
1615
return slow

0 commit comments

Comments
 (0)