Skip to content

Commit 952be29

Browse files
halfrosthalfrost
committed
Add solution 138 README
1 parent 9e037c6 commit 952be29

26 files changed

+1073
-699
lines changed

‎README.md

Lines changed: 471 additions & 470 deletions
Large diffs are not rendered by default.

‎leetcode/0138.Copy-List-With-Random-Pointer/138. Copy List With Random Pointer.go

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
package leetcode
22

3-
//执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
4-
//内存消耗：3.4 MB, 在所有 Go 提交中击败了100.00%的用户
3+
// Node define
54
type Node struct {
65
Val int
76
Next *Node
@@ -33,7 +32,6 @@ func copyNodeToLinkedList(head *Node) *Node {
3332
Next: cur.Next,
3433
}
3534
cur.Next, cur = node, cur.Next
36-
3735
}
3836
cur = head
3937
for cur != nil {

‎leetcode/0138.Copy-List-With-Random-Pointer/138. Copy List With Random Pointer_test.go

Lines changed: 109 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,115 @@
11
package leetcode
22

3-
import "testing"
3+
import (
4+
"fmt"
5+
"testing"
6+
7+
"github.com/halfrost/LeetCode-Go/structures"
8+
)
9+
10+
type question138 struct {
11+
para138
12+
ans138
13+
}
14+
15+
// para 是参数
16+
// one 代表第一个参数
17+
type para138 struct {
18+
head [][]int
19+
}
20+
21+
// ans 是答案
22+
// one 代表第一个答案
23+
type ans138 struct {
24+
one [][]int
25+
}
426

527
func Test_Problem138(t *testing.T) {
628

29+
qs := []question138{
30+
31+
{
32+
para138{[][]int{{7, structures.NULL}, {13, 0}, {11, 4}, {10, 2}, {1, 0}}},
33+
ans138{[][]int{{7, structures.NULL}, {13, 0}, {11, 4}, {10, 2}, {1, 0}}},
34+
},
35+
36+
{
37+
para138{[][]int{{1, 1}, {2, 1}}},
38+
ans138{[][]int{{1, 1}, {2, 1}}},
39+
},
40+
41+
{
42+
para138{[][]int{{3, structures.NULL}, {3, 0}, {3, structures.NULL}}},
43+
ans138{[][]int{{3, structures.NULL}, {3, 0}, {3, structures.NULL}}},
44+
},
45+
46+
{
47+
para138{[][]int{}},
48+
ans138{[][]int{}},
49+
},
50+
}
51+
52+
fmt.Printf("------------------------Leetcode Problem 138------------------------\n")
53+
54+
for _, q := range qs {
55+
_, p := q.ans138, q.para138
56+
fmt.Printf("【input】:%v 【output】:%v\n", p, node2Ints(copyRandomList(ints2Node(p.head))))
57+
}
58+
fmt.Printf("\n\n\n")
59+
}
60+
61+
func ints2Node(one [][]int) *Node {
62+
nodesMap := map[int]*Node{}
63+
for index, nodes := range one {
64+
tmp := &Node{Val: nodes[0]}
65+
nodesMap[index] = tmp
66+
}
67+
for index, node := range nodesMap {
68+
if index != len(one)-1 {
69+
node.Next = nodesMap[index+1]
70+
} else {
71+
node.Next = nil
72+
}
73+
}
74+
for index, nodes := range one {
75+
if nodes[1] == structures.NULL {
76+
nodesMap[index].Random = nil
77+
} else {
78+
nodesMap[index].Random = nodesMap[nodes[1]]
79+
}
80+
}
81+
return nodesMap[0]
82+
}
83+
84+
func node2Ints(head *Node) (res [][]int) {
85+
nodesMap, count, cur := map[*Node]int{}, 0, head
86+
if head == nil {
87+
return [][]int{}
88+
}
89+
for cur.Next != nil {
90+
nodesMap[cur] = count
91+
count++
92+
cur = cur.Next
93+
}
94+
nodesMap[cur] = count
95+
tmp := []int{}
96+
cur = head
97+
for cur.Next != nil {
98+
tmp := append(tmp, cur.Val)
99+
if cur.Random == nil {
100+
tmp = append(tmp, structures.NULL)
101+
} else {
102+
tmp = append(tmp, nodesMap[cur.Random])
103+
}
104+
res = append(res, tmp)
105+
cur = cur.Next
106+
}
107+
tmp = append(tmp, cur.Val)
108+
if cur.Random == nil {
109+
tmp = append(tmp, structures.NULL)
110+
} else {
111+
tmp = append(tmp, nodesMap[cur.Random])
112+
}
113+
res = append(res, tmp)
114+
return res
7115
}

‎leetcode/0138.Copy-List-With-Random-Pointer/README.md

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
# [138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)
2+
3+
## 题目
4+
5+
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
6+
7+
Return a **[deep copy](https://en.wikipedia.org/wiki/Object_copying#Deep_copy)** of the list.
8+
9+
The Linked List is represented in the input/output as a list of `n` nodes. Each node is represented as a pair of `[val, random_index]` where:
10+
11+
- `val`: an integer representing `Node.val`
12+
- `random_index`: the index of the node (range from `0` to `n-1`) where random pointer points to, or `null` if it does not point to any node.
13+
14+
**Example 1:**
15+
16+
![](https://assets.leetcode.com/uploads/2019/12/18/e1.png)
17+
18+
```
19+
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
20+
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
21+
22+
```
23+
24+
**Example 2:**
25+
26+
![](https://assets.leetcode.com/uploads/2019/12/18/e2.png)
27+
28+
```
29+
Input: head = [[1,1],[2,1]]
30+
Output: [[1,1],[2,1]]
31+
32+
```
33+
34+
**Example 3:**
35+
36+
![](https://assets.leetcode.com/uploads/2019/12/18/e3.png)
37+
38+
```
39+
Input: head = [[3,null],[3,0],[3,null]]
40+
Output: [[3,null],[3,0],[3,null]]
41+
42+
```
43+
44+
**Example 4:**
45+
46+
```
47+
Input: head = []
48+
Output: []
49+
Explanation: Given linked list is empty (null pointer), so return null.
50+
51+
```
52+
53+
**Constraints:**
54+
55+
- `10000 <= Node.val <= 10000`
56+
- `Node.random` is null or pointing to a node in the linked list.
57+
- The number of nodes will not exceed 1000.
58+
59+
## 题目大意
60+
61+
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。
62+
63+
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
64+
65+
- val：一个表示 Node.val 的整数。
66+
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
67+
68+
## 解题思路
69+
70+
- 这道题严格意义上是数据结构题，根据给定的数据结构，对它进行深拷贝。
71+
- 先将每个节点都复制一份，放在它的 next 节点中。如此穿插的复制一份链表。
72+
73+
![https://img.halfrost.com/Leetcode/leetcode_138_1_0.png](https://img.halfrost.com/Leetcode/leetcode_138_1_0.png)
74+
75+
再将穿插版的链表的 random 指针指向正确的位置。
76+
77+
![https://img.halfrost.com/Leetcode/leetcode_138_2.png](https://img.halfrost.com/Leetcode/leetcode_138_2.png)
78+
79+
再将穿插版的链表的 next 指针指向正确的位置。最后分开这交织在一起的两个链表的头节点，即可分开 2 个链表。
80+
81+
![https://img.halfrost.com/Leetcode/leetcode_138_3.png](https://img.halfrost.com/Leetcode/leetcode_138_3.png)
82+
83+
## 代码
84+
85+
```go
86+
package leetcode
87+
88+
// Node define
89+
type Node struct {
90+
Val int
91+
Next *Node
92+
Random *Node
93+
}
94+
95+
func copyRandomList(head *Node) *Node {
96+
if head == nil {
97+
return nil
98+
}
99+
tempHead := copyNodeToLinkedList(head)
100+
return splitLinkedList(tempHead)
101+
}
102+
103+
func splitLinkedList(head *Node) *Node {
104+
cur := head
105+
head = head.Next
106+
for cur != nil && cur.Next != nil {
107+
cur.Next, cur = cur.Next.Next, cur.Next
108+
}
109+
return head
110+
}
111+
112+
func copyNodeToLinkedList(head *Node) *Node {
113+
cur := head
114+
for cur != nil {
115+
node := &Node{
116+
Val: cur.Val,
117+
Next: cur.Next,
118+
}
119+
cur.Next, cur = node, cur.Next
120+
}
121+
cur = head
122+
for cur != nil {
123+
if cur.Random != nil {
124+
cur.Next.Random = cur.Random.Next
125+
}
126+
cur = cur.Next.Next
127+
}
128+
return head
129+
}
130+
```

‎website/content/ChapterFour/0137.Single-Number-II.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -112,5 +112,5 @@ func singleNumberIIIII1(nums []int) int {
112112
----------------------------------------------
113113
<div style="display: flex;justify-content: space-between;align-items: center;">
114114
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0136.Single-Number/">⬅️上一页</a></p>
115-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0141.Linked-List-Cycle/">下一页➡️</a></p>
115+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0138.Copy-List-With-Random-Pointer/">下一页➡️</a></p>
116116
</div>

0 commit comments

Comments
 (0)