reorder_list

hitzzc · hitzzc · commit 69919f14c690 · 2016-10-12T21:37:37.000+08:00
diff --git a/README.md b/README.md
@@ -126,6 +126,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [140. word break II](https://github.com/hitzzc/go-leetcode/tree/master/word_break_II)
 #### [141. Linked List Cycle](https://github.com/hitzzc/go-leetcode/tree/master/linked_list_cycle)
 #### [142. Linked List Cycle II](https://github.com/hitzzc/go-leetcode/tree/master/linked_list_cycle_II)
+#### [143. reorder list](https://github.com/hitzzc/go-leetcode/tree/master/reorder_list)
 
 
 
diff --git a/reorder_list/reorder_list.go b/reorder_list/reorder_list.go
@@ -0,0 +1,42 @@
+package reorder_list
+
+type ListNode struct {
+	Val  int
+	Next *ListNode
+}
+
+func reorderList(head *ListNode) {
+	slow, fast := head, head
+	var tail *ListNode
+	for fast != nil && fast.Next != nil {
+		tail = slow
+		slow = slow.Next
+		fast = fast.Next.Next
+	}
+	if tail != nil {
+		tail.Next = nil
+	}
+	var secondHead *ListNode
+	fast = slow
+	for fast != nil {
+		slow = fast
+		fast = fast.Next
+		slow.Next = secondHead
+		secondHead = slow
+	}
+	firstHead := head
+	var p1, p2 *ListNode
+	for firstHead != nil && secondHead != nil {
+		p1 = firstHead.Next
+		p2 = secondHead.Next
+		firstHead.Next = secondHead
+		secondHead.Next = p1
+		if p1 == nil {
+			secondHead.Next = p2
+			break
+		}
+		firstHead = p1
+		secondHead = p2
+	}
+	return
+}
