sort_list

hitzzc · hitzzc · commit 4959dba352e5 · 2016-10-13T17:27:54.000+08:00
diff --git a/README.md b/README.md
@@ -131,6 +131,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [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)
+#### [148. sort list](https://github.com/hitzzc/go-leetcode/tree/master/sort_list)
 
 
 
diff --git a/sort_list/sort_list.go b/sort_list/sort_list.go
@@ -0,0 +1,59 @@
+package sort_list
+
+type ListNode struct {
+	Val  int
+	Next *ListNode
+}
+
+func sortList(head *ListNode) *ListNode {
+	if head == nil || head.Next == nil {
+		return head
+	}
+	secHead := split(head)
+	return merge(sortList(head), sortList(secHead))
+}
+
+func split(head *ListNode) *ListNode {
+	if head == nil || head.Next == nil {
+		return nil
+	}
+	slow, fast := head, head
+	var tail *ListNode
+	for fast != nil && fast.Next != nil {
+		tail = slow
+		slow = slow.Next
+		fast = fast.Next.Next
+	}
+	tail.Next = nil
+	return slow
+}
+
+func merge(left, right *ListNode) (head *ListNode) {
+	if left == nil {
+		return right
+	} else if right == nil {
+		return left
+	}
+	var p, cur *ListNode
+	for left != nil && right != nil {
+		if left.Val < right.Val {
+			cur = left
+			left = left.Next
+		} else {
+			cur = right
+			right = right.Next
+		}
+		if head == nil {
+			head = cur
+		} else {
+			p.Next = cur
+		}
+		p = cur
+	}
+	if left != nil {
+		p.Next = left
+	} else {
+		p.Next = right
+	}
+	return head
+}
