Skip to content

Commit 30f5f7d

Browse files
committed
insertion_sort_list
1 parent 793ac29 commit 30f5f7d

File tree

3 files changed

+65
-0
lines changed

3 files changed

+65
-0
lines changed

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -130,6 +130,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
130130
#### [144. binary tree preorder traversal](https://github.com/hitzzc/go-leetcode/tree/master/binary_tree_preorder_traversal)
131131
#### [145. binary tree postorder traversal](https://github.com/hitzzc/go-leetcode/tree/master/binary_tree_postorder_traversal)
132132
#### [146. LRU Cache](https://github.com/hitzzc/go-leetcode/tree/master/lru_cache)
133+
#### [147. insertion sort list](https://github.com/hitzzc/go-leetcode/tree/master/insertion_sort_list)
133134

134135

135136

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package insertion_sort_list
2+
3+
type ListNode struct {
4+
Val int
5+
Next *ListNode
6+
}
7+
8+
func insertionSortList(head *ListNode) *ListNode {
9+
if head == nil || head.Next == nil {
10+
return head
11+
}
12+
fake := &ListNode{Next: head}
13+
tail := head
14+
var cur *ListNode
15+
for tail.Next != nil {
16+
cur = tail.Next
17+
p := fake
18+
for ; p.Next != cur; p = p.Next {
19+
if p.Next.Val >= cur.Val {
20+
tmp := p.Next
21+
p.Next = cur
22+
tail.Next = cur.Next
23+
cur.Next = tmp
24+
break
25+
}
26+
}
27+
if p == tail {
28+
tail = cur
29+
}
30+
}
31+
return fake.Next
32+
}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package insertion_sort_list
2+
3+
import (
4+
"testing"
5+
)
6+
7+
func (this *ListNode) insert(val int) {
8+
p := this
9+
for p.Next != nil {
10+
p = p.Next
11+
}
12+
p.Next = &ListNode{Val: val}
13+
}
14+
15+
func (this *ListNode) print() {
16+
p := this
17+
for p != nil {
18+
println(p.Val)
19+
p = p.Next
20+
}
21+
}
22+
23+
func TestInsertionSortList(t *testing.T) {
24+
head := &ListNode{Val: 3}
25+
head.insert(2)
26+
head.insert(1)
27+
head.insert(4)
28+
head.insert(5)
29+
head.insert(1)
30+
head = insertionSortList(head)
31+
head.print()
32+
}

0 commit comments

Comments
 (0)