Untitled

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func ToList(arr []int) *ListNode {
	if len(arr) == 0 {
		return nil
	}
	head := &ListNode{
		Val:  arr[0],
		Next: nil,
	}
	runPtr := head
	for i := 1; i < len(arr); i++ {
		runPtr.Next = &ListNode{
			Val:  arr[i],
			Next: nil,
		}
		runPtr = runPtr.Next
	}
	return head
}

func PrintList(head *ListNode) {
	arr := []int{}
	for head != nil {
		arr = append(arr, head.Val)
		head = head.Next
	}
	fmt.Println(arr)
}

func reverseList(head *ListNode) *ListNode {
	current := head
	if current == nil {
		return nil
	}
	var next *ListNode
	var prev *ListNode
	for current != nil {
		next = current.Next
		current.Next = prev
		prev = current
		current = next
	}
	return prev
}

func getMiddleNode(head *ListNode) *ListNode {
	turtle, rabbit := head, head
	if head != nil {
		for rabbit != nil && rabbit.Next != nil {
			rabbit = rabbit.Next.Next
			turtle = turtle.Next
		}
	}
	return turtle
}

func reorderList(head *ListNode) {
	start := head
	mid := getMiddleNode(head)
	nextMid := mid.Next
	mid.Next = nil

	mid = reverseList(nextMid)
	next := head

	for head != nil && mid != nil {
		next = head.Next
		head.Next = mid
		mid = mid.Next
		head.Next.Next = next
		head = next
	}
	PrintList(start)
}

func main() {
	arr := []int{1, 2, 3, 4, 5, 6, 7}
	// result := []int{1, 7, 2, 6, 3, 5, 4}
	head := ToList(arr)
	PrintList(head)
	// head = head.Next
	// PrintList(reverseList(head))
	// fmt.Println(getMiddleNode(head))

	reorderList(head)
}