/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func getMiddleNode(head *ListNode) *ListNode {
	slow, fast := head, head

	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	return slow
}

func reverseList(head *ListNode) *ListNode {

	var previous *ListNode
	current := head

	for current != nil {
		next := current.Next

		//reverse a single connection
		current.Next = previous

		previous = current
		current = next
	}

	return previous
}

func isPalindrome(head *ListNode) bool {

	if head == nil || head.Next == nil {
		return true
	}

	// 1. find out middle of list
	// using slow and fast pointer approach
	middle := getMiddleNode(head)

	// 2. reverse one of the half
	// 2nd half
	head2 := reverseList(middle)

	// 3. traverse and comparse 2 list and check if any element not
	//   matching while increasing next pointers

	head1 := head
	for head2 != nil {
		if head1.Val != head2.Val {
			return false
		}
		head2 = head2.Next
		head1 = head1.Next
	}

	return true
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func checkPalindrome(current *ListNode, front **ListNode) bool {
	if current == nil {
		return true
	}

	if !checkPalindrome(current.Next, front) {
		return false
	}

	if current.Val != (*front).Val {
		return false
	}

	(*front) = (*front).Next
	return true
}

func isPalindrome(head *ListNode) bool {

	if head == nil || head.Next == nil {
		return true
	}

	front := &head
	current := head
	return checkPalindrome(current, front)
}