Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit666698f

Browse files
authored
Merge pull request6boris#81 from kylesliu/develop
add some problem solution
2 parents9965932 +119253b commit666698f

File tree

16 files changed

+498
-186
lines changed

16 files changed

+498
-186
lines changed

‎src/0092.Reverse-Linked-List-II/ListNode.go

Lines changed: 10 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -10,14 +10,14 @@ type ListNode struct {
1010
Next*ListNode
1111
}
1212

13-
//正确解
14-
funcSolution(head*ListNode)*ListNode {
15-
varprev*ListNode
16-
forhead!=nil {
17-
head.Next,prev,head=prev,head,head.Next
18-
}
19-
returnprev
20-
}
13+
////正确解
14+
//func Solution(head *ListNode) *ListNode {
15+
//var prev *ListNode
16+
//for head != nil {
17+
//head.Next, prev, head = prev, head, head.Next
18+
//}
19+
//return prev
20+
//}
2121

2222
//比较结果
2323
funcisEqual(l1*ListNode,l2*ListNode)bool {
@@ -46,6 +46,7 @@ func PrintList(head *ListNode) {
4646
fmt.Println()
4747
}
4848

49+
4950
//更具数组反序列化链表
5051
funcUnmarshalListBySlice(nums []int)*ListNode {
5152
head:=&ListNode{Val:-1,Next:nil}
@@ -68,3 +69,4 @@ func UnmarshalListByRand(max_num int, len int) *ListNode {
6869
}
6970
returnhead.Next
7071
}
72+

‎src/0092.Reverse-Linked-List-II/README.md

Lines changed: 22 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -4,50 +4,47 @@
44

55
Reverse a linked list from position m to n. Do it in one-pass.
66

7+
**Note:** 1 ≤ m ≤ n ≤ length of list.\
78
Note: 1 ≤ m ≤ n ≤ length of list.
8-
99
**Example 1:**
1010

1111
```
1212
Input: 1->2->3->4->5->NULL, m = 2, n = 4
1313
Output: 1->4->3->2->5->NULL
1414
```
1515

16-
**Tags:**Math, String
16+
**Tags:**Linked List
1717

1818
##题意
19+
>给定一个单链表和两个数字 m 和 n，反转链表 m 到 n 的部分。
1920
>请将链表中第 nn 个节点和第 mm 个节点之间的部分翻转。
2021
链表最多只能遍历一遍。
2122

2223
##题解
2324

2425
###思路1
25-
>和problem 206类似
26+
1. 链表先走 m 步，到达开始反转的起点，并记录下前一个节点和反转开始的节点。
27+
1. 开始反转链表，反转的长度位 n - m。
28+
1. 把链表连起来。
2629

2730
```go
2831
funcreverseBetween(head *ListNode,mint,nint) *ListNode {
29-
if m == n {
30-
return head
31-
}
32-
dummy:=new(ListNode)
33-
head, dummy.Next = dummy, head
34-
35-
fori:=0; i < m-1; i++ {
36-
head = head.Next
37-
}
38-
varcurr,prev *ListNode = head.Next,nil
39-
fori:=0; i < n-m+1; i++ {
40-
next:= curr.Next
41-
curr.Next = prev
42-
prev = curr
43-
curr = next
44-
}
45-
head.Next.Next = curr
46-
head.Next = prev
47-
48-
return dummy.Next
32+
newHead:=new(ListNode)
33+
newHead.Next = head
34+
current:= newHead
35+
fori:=0; i < m -1; i++ {
36+
current = current.Next
37+
}
38+
39+
prev:= current
40+
current = current.Next
41+
fori:=0; i < n - m; i++ {
42+
node:= &ListNode{current.Next.Val, prev.Next}
43+
prev.Next = node
44+
current.Next = current.Next.Next
45+
}
46+
return newHead.Next
4947
}
50-
5148
```
5249

5350
###思路2
@@ -60,5 +57,5 @@ func reverseBetween(head *ListNode, m int, n int) *ListNode {
6057

6158
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
6259

63-
[title]:https://leetcode.com/problems/two-sum/description/
60+
[title]:https://leetcode.com/problems/reverse-linked-list-ii/description/
6461
[me]:https://github.com/kylesliu/awesome-golang-leetcode

‎src/0092.Reverse-Linked-List-II/Solution.go

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,23 @@
11
package Solution
22

3+
funcSolution(head*ListNode,m,nint)*ListNode {
4+
newHead:=new(ListNode)
5+
newHead.Next=head
6+
current:=newHead
7+
8+
fori:=0;i<m-1;i++ {
9+
current=current.Next
10+
}
11+
prev:=current
12+
current=current.Next
13+
14+
fori:=0;i<n-m;i++ {
15+
node:=&ListNode{current.Next.Val,prev.Next}
16+
prev.Next=node
17+
current.Next=current.Next.Next
18+
}
19+
returnnewHead.Next
20+
}
321
/**
422
* Definition for singly-linked list.
523
* type ListNode struct {

‎src/0092.Reverse-Linked-List-II/Solution_test.go

Lines changed: 21 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,41 @@
11
package Solution
22

33
import (
4-
"reflect"
54
"testing"
65
)
76

7+
typeInputCasestruct {
8+
element []int
9+
mint
10+
nint
11+
}
12+
813
funcTestSolution(t*testing.T) {
914
//测试用例
1015
cases:= []struct {
1116
namestring
12-
inputsListNode
13-
mint
14-
nint
15-
expectListNode
17+
inputsInputCase
18+
expect []int
1619
}{
17-
{"TestCase 1",ListNode{
18-
Val:1,
19-
Next:&ListNode{Val:2,
20-
Next:&ListNode{Val:3,
21-
Next:&ListNode{Val:4,Next:&ListNode{Val:5,Next:nil}},
22-
}},
23-
},2,4,ListNode{}},
20+
{
21+
"TestCase 1",
22+
InputCase{
23+
[]int{1,2,3,4,5},
24+
2,
25+
4,
26+
},
27+
[]int{1,4,3,2,5},
28+
},
2429
}
2530

2631
//开始测试
2732
for_,c:=rangecases {
2833
t.Run(c.name,func(t*testing.T) {
29-
ret:=reverseBetween(&c.inputs,c.m,c.n)
30-
if!reflect.DeepEqual(ret,c.expect) {
34+
ret:=Solution(UnmarshalListBySlice(c.inputs.element),c.inputs.m,c.inputs.n)
35+
if!isEqual(ret,UnmarshalListBySlice(c.expect)) {
3136
PrintList(ret)
32-
//t.Fatalf("expected: %v, but got: %v, with inputs: %v",
33-
//c.expect, ret, c.inputs)
37+
PrintList(UnmarshalListBySlice(c.expect))
38+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",c.expect,ret,c.inputs)
3439
}
3540
})
3641
}

‎src/0138.Copy-List-with-Random-Pointer/Node.cpp

Lines changed: 0 additions & 14 deletions
This file was deleted.

‎src/0138.Copy-List-with-Random-Pointer/Solution.cpp

Lines changed: 0 additions & 90 deletions
This file was deleted.
Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package Solution
2+
3+
///*
4+
//// Definition for a Node.
5+
//class Node {
6+
//public:
7+
// int val;
8+
// Node* next;
9+
// Node* random;
10+
//
11+
// Node() {}
12+
//
13+
// Node(int _val, Node* _next, Node* _random) {
14+
// val = _val;
15+
// next = _next;
16+
// random = _random;
17+
// }
18+
//};
19+
//*/
20+
//class Solution {
21+
//public:
22+
// Node* copyRandomList(Node* head) {
23+
//
24+
// }
25+
// RandomListNode *copyRandomList(RandomListNode *head) {
26+
// RandomListNode *newHead, *l1, *l2;
27+
// if (head == NULL) return NULL;
28+
// for (l1 = head; l1 != NULL; l1 = l1->next->next) {
29+
// l2 = new RandomListNode(l1->label);
30+
// l2->next = l1->next;
31+
// l1->next = l2;
32+
// }
33+
//
34+
// newHead = head->next;
35+
// for (l1 = head; l1 != NULL; l1 = l1->next->next) {
36+
// if (l1->random != NULL) l1->next->random = l1->random->next;
37+
// }
38+
//
39+
// for (l1 = head; l1 != NULL; l1 = l1->next) {
40+
// l2 = l1->next;
41+
// l1->next = l2->next;
42+
// if (l2->next != NULL) l2->next = l2->next->next;
43+
// }
44+
//
45+
// return newHead;
46+
// }
47+
// RandomListNode *copyRandomList_2(RandomListNode *head) {
48+
// RandomListNode *newHead, *l1, *l2;
49+
// if (head == NULL) return NULL;
50+
// /*origin
51+
// l11 - 2 - 3 NULL
52+
// rand p \ |
53+
// l11 - 2 - 3 NULL
54+
// */
55+
//
56+
// /*connect
57+
// l21 2 3 NULL
58+
// next p \ |
59+
// l11 - 2 - 3 NULL
60+
// rand p | | |
61+
// l21 2 3 NULL
62+
// */
63+
// for (l1 = head; l1 != NULL; l1 = l1->next) {
64+
// l2 = new RandomListNode(l1->label);
65+
// l2->next = l1->random;
66+
// l1->random = l2;
67+
// }
68+
//
69+
// /* build rand p
70+
// l21 2 3 NULL
71+
// next p \ |
72+
// l11 - 2 - 3 NULL
73+
// rand p | | |
74+
// l21 2 3 NULL
75+
// rand p \ |
76+
// l21 2 3 NULL
77+
// */
78+
// newHead = head->random;
79+
// for (l1 = head; l1 != NULL; l1 = l1->next) {
80+
// l2 = l1->random;
81+
// l2->random = l2->next ? l2->next->random : NULL;
82+
// }
83+
// /* restore */
84+
// for (l1 = head; l1 != NULL; l1 = l1->next) {
85+
// l2 = l1->random;
86+
// l1->random = l2->next;
87+
// l2->next = l1->next ? l1->next->random : NULL;
88+
// }
89+
//
90+
// return newHead;
91+
// }
92+
//};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp