Skip to content

Commit 76ffe7d

Browse files
fritxfritx
committed
feat: add linkedlist demo
1 parent 43ed03f commit 76ffe7d

File tree

2 files changed

+199
-0
lines changed

2 files changed

+199
-0
lines changed

‎public/code/index.yml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
- linkedlist.tsx
12
- resume.md
23
- vditor-charts.md
34
- vditor-sequence.md

‎public/code/linkedlist.tsx‎

Lines changed: 198 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,198 @@
1+
/** @jsx React.createElement */
2+
/* global React */
3+
4+
appendCss(`
5+
section { margin-bottom: 20px }
6+
`)
7+
8+
let sections = [
9+
// 141. 环形链表 - 双指针-快慢指针
10+
() => {
11+
function detectCycle<T>(head: ListNode<T>): boolean {
12+
let fast = head
13+
let slow = head
14+
while (fast && fast.next) {
15+
fast = fast.next.next ? fast.next.next : null
16+
slow = slow.next ? slow.next : null
17+
if (fast && slow && fast.value === slow.value) return true
18+
}
19+
return false
20+
}
21+
let before = createLinkedListWithCycle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
22+
let before1 = createLinkedListWithCycle([1, 2, 3, 4, 5, 6, 7, 8, 9, 7])
23+
let after = detectCycle(before)
24+
let after1 = detectCycle(before1)
25+
return (
26+
<section>
27+
<h4>141. 环形链表</h4>
28+
<div>{stringifyLinkedListWithCycle(before)}</div>
29+
<div>Detect cycle: {String(after)}</div>
30+
<div>{stringifyLinkedListWithCycle(before1)}</div>
31+
<div>Detect cycle: {String(after1)}</div>
32+
</section>
33+
)
34+
},
35+
36+
// 142. 环形链表 II - 双指针-快慢指针
37+
() => {
38+
function detectCycleListNode<T>(head: ListNode<T>): ListNode<T> {
39+
let fast = head
40+
let slow = head
41+
while (fast && fast.next) {
42+
fast = fast.next.next ? fast.next.next : null
43+
slow = slow.next ? slow.next : null
44+
if (fast && slow && fast.value === slow.value) { // intersected - has cycle
45+
let start = head
46+
while (start.next) {
47+
start = start.next
48+
slow = slow.next
49+
if (start && slow && start.value === slow.value) { // intersected - get node
50+
return slow
51+
}
52+
}
53+
}
54+
}
55+
return null
56+
}
57+
let before = createLinkedListWithCycle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
58+
let before1 = createLinkedListWithCycle([1, 2, 3, 4, 5, 6, 7, 8, 9, 7])
59+
let after = detectCycleListNode(before)
60+
let after1 = detectCycleListNode(before1)
61+
return (
62+
<section>
63+
<h4>142. 环形链表 II</h4>
64+
<div>{stringifyLinkedListWithCycle(before)}</div>
65+
<div>Cycle-node: {stringifyListNode(after)}</div>
66+
<div>{stringifyLinkedListWithCycle(before1)}</div>
67+
<div>Cycle-node: {stringifyListNode(after1)}</div>
68+
</section>
69+
)
70+
},
71+
72+
// 206. 反转链表
73+
() => {
74+
function reverseLinkedList<T>(head: ListNode<T>): ListNode<T> {
75+
head = _.cloneDeep(head)
76+
let prev = null
77+
let curr = head
78+
while (curr) {
79+
let next = curr.next
80+
curr.next = prev
81+
prev = curr
82+
curr = next
83+
}
84+
return prev
85+
}
86+
let before = createLinkedList([1, 2, 3, 4])
87+
let after = reverseLinkedList(before)
88+
return (
89+
<section>
90+
<h4>206. 反转链表</h4>
91+
<div>{stringifyLinkedList(before)}</div>
92+
<div>Reverse: {stringifyLinkedList(after)}</div>
93+
</section>
94+
)
95+
},
96+
97+
// 876. 链表的中间节点 - 双指针-快慢指针
98+
() => {
99+
function getMiddleListNode<T>(head: ListNode<T>): ListNode<T> {
100+
let fast = head
101+
let slow = head
102+
while (fast && fast.next) {
103+
fast = fast.next.next ? fast.next.next : null
104+
slow = slow.next ? slow.next : slow
105+
}
106+
return slow
107+
}
108+
let before = createLinkedList([1, 2, 3, 4, 5, 6, 7])
109+
let before1 = createLinkedList([1, 2, 3, 4, 5, 6, 7, 8])
110+
let middle = getMiddleListNode(before)
111+
let middle1 = getMiddleListNode(before1)
112+
return (
113+
<section>
114+
<h4>876. 链表的中间节点</h4>
115+
<div>{stringifyLinkedList(before)}</div>
116+
<div>Middle-node: {(middle.value)}</div>
117+
<div>{stringifyLinkedList(before1)}</div>
118+
<div>Middle-node: {(middle1.value)}</div>
119+
</section>
120+
)
121+
}
122+
]
123+
124+
let App = () => {
125+
return (
126+
<main style={{ padding: 20 }}>
127+
{sections.map((Comp, idx) => {
128+
return <Comp key={idx} />
129+
})}
130+
</main>
131+
)
132+
}
133+
134+
interface ListNode<T = any> {
135+
value: T
136+
next: ListNode<T>
137+
}
138+
function createLinkedListWithCycle<T>(arr: T[]): ListNode<T> {
139+
let head = null
140+
let prev = null
141+
let cache = new Map<T, ListNode<T>>()
142+
arr.forEach(val => {
143+
let curr: ListNode
144+
if (cache.has(val)) {
145+
curr = cache.get(val)
146+
} else {
147+
curr = { value: val, next: null }
148+
cache.set(val, curr)
149+
}
150+
if (prev) {
151+
prev.next = curr
152+
} else {
153+
head = curr
154+
}
155+
prev = curr
156+
})
157+
return head
158+
}
159+
function createLinkedList<T>(arr: T[]): ListNode<T> {
160+
let head = null
161+
let prev = null
162+
arr.forEach(val => {
163+
let curr: ListNode = { value: val, next: null }
164+
if (prev) {
165+
prev.next = curr
166+
} else {
167+
head = curr
168+
}
169+
prev = curr
170+
})
171+
return head
172+
}
173+
function stringifyLinkedListWithCycle<T>(head: ListNode<T>): string {
174+
let arr = []
175+
let curr = head
176+
let cache = new Set<T>()
177+
while (curr) {
178+
let val = curr.value
179+
let taken = cache.has(val)
180+
cache.add(val)
181+
arr.push(val)
182+
if (taken) break
183+
curr = curr.next
184+
}
185+
return arr.join(' -> ')
186+
}
187+
function stringifyLinkedList<T>(head: ListNode<T>): string {
188+
let arr = []
189+
let curr = head
190+
while (curr) {
191+
arr.push(curr.value)
192+
curr = curr.next
193+
}
194+
return arr.join(' -> ')
195+
}
196+
function stringifyListNode<T>(head: ListNode<T>): string {
197+
return String(head ? head.value : null)
198+
}

0 commit comments

Comments
 (0)