package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderListOld(head *ListNode) {
	// Given a singly linked list L: L0→L1→…→Ln-1→Ln,
	// reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
	if head == nil || head.Next == nil {
		return
	}
	stack := make([]*ListNode, 0)
	beg := head
	length := 0
	for beg != nil {
		stack = append(stack, beg)
		beg = beg.Next
		length++
	}
	beg = head
	for i := 0; i < length/2; i++ {
		tmp := beg.Next
		beg.Next = stack[length-i-1]
		beg.Next.Next = tmp
		beg = tmp
	}
	beg.Next = nil
}

func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		// Find the middle of list
		slow = slow.Next
		fast = fast.Next.Next
	}
	// Reverse the 2nd part
	var prev *ListNode
	for slow.Next != nil {
		tmp := slow.Next
		slow.Next = prev
		prev = slow
		slow = tmp
	}
	slow.Next = prev
	// Merge the 1st part and the 2nd part
	left, right := head, slow
	for left != nil && right.Next != nil {
		tmpL, tmpR := left.Next, right.Next
		left.Next = right
		right.Next = tmpL
		left, right = tmpL, tmpR
	}
}

// func main() {
// 	n5 := ListNode{5, nil}
// 	n4 := ListNode{4, &n5}
// 	// n4 := ListNode{4, nil}
// 	n3 := ListNode{3, &n4}
// 	n2 := ListNode{2, &n3}
// 	n1 := ListNode{1, &n2}
// 	printList(&n1)
// 	reorderList(&n1)
// 	printList(&n1)
// }