insertion_sort_list

hitzzc · hitzzc · commit 30f5f7de8dca · 2016-10-13T16:45:27.000+08:00
diff --git a/README.md b/README.md
@@ -130,6 +130,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [144. binary tree preorder traversal](https://github.com/hitzzc/go-leetcode/tree/master/binary_tree_preorder_traversal)
 #### [145. binary tree postorder traversal](https://github.com/hitzzc/go-leetcode/tree/master/binary_tree_postorder_traversal)
 #### [146. LRU Cache](https://github.com/hitzzc/go-leetcode/tree/master/lru_cache)
+#### [147. insertion sort list](https://github.com/hitzzc/go-leetcode/tree/master/insertion_sort_list)
 
 
 
diff --git a/insertion_sort_list/insertion_sort_list.go b/insertion_sort_list/insertion_sort_list.go
@@ -0,0 +1,32 @@
+package insertion_sort_list
+
+type ListNode struct {
+	Val  int
+	Next *ListNode
+}
+
+func insertionSortList(head *ListNode) *ListNode {
+	if head == nil || head.Next == nil {
+		return head
+	}
+	fake := &ListNode{Next: head}
+	tail := head
+	var cur *ListNode
+	for tail.Next != nil {
+		cur = tail.Next
+		p := fake
+		for ; p.Next != cur; p = p.Next {
+			if p.Next.Val >= cur.Val {
+				tmp := p.Next
+				p.Next = cur
+				tail.Next = cur.Next
+				cur.Next = tmp
+				break
+			}
+		}
+		if p == tail {
+			tail = cur
+		}
+	}
+	return fake.Next
+}
diff --git a/insertion_sort_list/insertion_sort_list_test.go b/insertion_sort_list/insertion_sort_list_test.go
@@ -0,0 +1,32 @@
+package insertion_sort_list
+
+import (
+	"testing"
+)
+
+func (this *ListNode) insert(val int) {
+	p := this
+	for p.Next != nil {
+		p = p.Next
+	}
+	p.Next = &ListNode{Val: val}
+}
+
+func (this *ListNode) print() {
+	p := this
+	for p != nil {
+		println(p.Val)
+		p = p.Next
+	}
+}
+
+func TestInsertionSortList(t *testing.T) {
+	head := &ListNode{Val: 3}
+	head.insert(2)
+	head.insert(1)
+	head.insert(4)
+	head.insert(5)
+	head.insert(1)
+	head = insertionSortList(head)
+	head.print()
+}
