8000 Merge pull request #729 from 0xff-dev/2095 · 6boris/awesome-golang-algorithm@11222b2 · GitHub
[go: up one dir, main page]
Skip to content

Commit 11222b2

Browse files
6boris6boris
authored
Merge pull request #729 from 0xff-dev/2095
Add solution and test-cases for problem 2095
2 parents c8605a9 + ee65e3d commit 11222b2

File tree

6 files changed

+112
-22
lines changed

6 files changed

+112
-22
lines changed

‎leetcode/2001-2100/2095.Delete-the-Middle-Node-of-a-Linked-List/README.md

Lines changed: 34 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,49 @@
11
# [2095.Delete the Middle Node of a Linked List][title]
22

3-
> [!WARNING|style:flat]
4-
> This question is temporarily unanswered if you have good ideas. Welcome to [Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
5-
63
## Description
4+
You are given the `head` of a linked list. **Delete** the **middle node**, and return the `head` of the modified linked list.
5+
6+
The **middle node** of a linked list of size `n` is the `⌊n / 2⌋th` node from the **start** using **0-based indexing**, where `⌊x⌋` denotes the largest integer less than or equal to `x`.
7+
8+
- For `n` = `1`, `2`, `3`, `4`, and `5`, the middle nodes are `0`, `1`, `1`, `2`, and `2`, respectively.
79

8-
**Example 1:**
10+
**Example 1:**
11+
12+
![1](./eg1drawio.png)
913

1014
```
11-
Input: a = "11", b = "1"
12-
Output: "100"
15+
Input: head = [1,3,4,7,1,2,6]
16+
Output: [1,3,4,1,2,6]
17+
Explanation:
18+
The above figure represents the given linked list. The indices of the nodes are written below.
19+
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
20+
We return the new list after removing this node.
1321
```
1422

15-
## 题意
16-
> ...
23+
**Example 2:**
1724

18-
## 题解
25+
![2](./eg2drawio.png)
1926

20-
### 思路1
21-
> ...
22-
Delete the Middle Node of a Linked List
23-
```go
27+
```
28+
Input: head = [1,2,3,4]
29+
Output: [1,2,4]
30+
Explanation:
31+
The above figure represents the given linked list.
32+
For n = 4, node 2 with value 3 is the middle node, which is marked in red.
2433
```
2534

35+
**Example 3:**
36+
37+
![3](./eg3drawio.png)
38+
39+
```
40+
Input: head = [2,1]
41+
Output: [2]
42+
Explanation:
43+
The above figure represents the given linked list.
44+
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
45+
Node 0 with value 2 is the only node remaining after removing node 1.
46+
```
2647

2748
## 结语
2849

‎leetcode/2001-2100/2095.Delete-the-Middle-Node-of-a-Linked-List/Solution.go

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,24 @@
11
package Solution
22

3-
func Solution(x bool) bool {
4-
return x
3+
type ListNode struct {
4+
Val int
5+
Next *ListNode
6+
}
7+
8+
func Solution(head *ListNode) *ListNode {
9+
if head == nil || head.Next == nil {
10+
return nil
11+
}
12+
13+
pre, cur := head, head
14+
for cur != nil && cur.Next != nil {
15+
pre = pre.Next
16+
cur = cur.Next.Next
17+
}
18+
if pre.Next == nil {
19+
head.Next = nil
20+
} else {
21+
*pre = *(pre.Next)
22+
}
23+
return head
524
}

‎leetcode/2001-2100/2095.Delete-the-Middle-Node-of-a-Linked-List/Solution_test.go

Lines changed: 57 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -10,12 +10,62 @@ func TestSolution(t *testing.T) {
1010
// 测试用例
1111
cases := []struct {
1212
name string
13-
inputs bool
14-
expect bool
13+
inputs *ListNode
14+
expect *ListNode
1515
}{
16-
{"TestCase", true, true},
17-
{"TestCase", true, true},
18-
{"TestCase", false, false},
16+
{"TestCase1", &ListNode{
17+
Val: 1,
18+
Next: &ListNode{
19+
Val: 3,
20+
Next: &ListNode{
21+
Val: 4,
22+
Next: &ListNode{
23+
Val: 7,
24+
Next: &ListNode{
25+
Val: 1,
26+
Next: &ListNode{
27+
Val: 2,
28+
Next: &ListNode{Val: 6},
29+
},
30+
},
31+
},
32+
},
33+
},
34+
}, &ListNode{
35+
Val: 1,
36+
Next: &ListNode{
37+
Val: 3,
38+
Next: &ListNode{
39+
Val: 4,
40+
Next: &ListNode{
41+
Val: 1,
42+
Next: &ListNode{
43+
Val: 2,
44+
Next: &ListNode{Val: 6},
45+
},
46+
},
47+
},
48+
},
49+
}},
50+
{"TestCase2", &ListNode{
51+
Val: 1,
52+
Next: &ListNode{
53+
Val: 2,
54+
Next: &ListNode{
55+
Val: 3,
56+
Next: &ListNode{Val: 4},
57+
},
58+
},
59+
}, &ListNode{
60+
Val: 1,
61+
Next: &ListNode{
62+
Val: 2,
63+
Next: &ListNode{
64+
Val: 4,
65+
},
66+
},
67+
}},
68+
{"TestCase3", &ListNode{Val: 2, Next: &ListNode{Val: 1}}, &ListNode{Val: 2}},
1969
}
2070

2171
// 开始测试
@@ -30,10 +80,10 @@ func TestSolution(t *testing.T) {
3080
}
3181
}
3282

33-
// 压力测试
83+
// 压力测试
3484
func BenchmarkSolution(b *testing.B) {
3585
}
3686

37-
// 使用案列
87+
// 使用案列
3888
func ExampleSolution() {
3989
}

‎leetcode/2001-2100/2095.Delete-the-Middle-Node-of-a-Linked-List/eg1drawio.png

16.2 KB
Loading

‎leetcode/2001-2100/2095.Delete-the-Middle-Node-of-a-Linked-List/eg2drawio.png

9.86 KB
Loading

‎leetcode/2001-2100/2095.Delete-the-Middle-Node-of-a-Linked-List/eg3drawio.png

7.04 KB
Loading

0 commit comments

Comments
 (0)
0