# Check Middle Of Linked List

/* The brute force solution is counting the number of nodes in the Linked List, and then finding the middle in the second iteration. 
 * We can do it in one iteration using the tortoise and the hare (slow and fast) problem solving pattern

1. Have two pointers, both starting at the first node
2. One pointer moves 2 nodes (hare), one moves one node (tortoise)
3. When the hare reaches the end, the tortoise will be at the middle

*/ 
const middle = (linkedlist) => {
  let slow = linkedlist.head
  let fast = linkedlist.head

  while (fast !== null && fast.next !== null) {
    console.log('hello')
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.value;
}

# Check if List is a Palindrome

/*
 *

We will use the solution we used to find the middle of the Middle of the Linked List: https://repl.it/join/ihcufzfi-b17z

1. When we have the middle node, reverse the second half of the list
2. Compare the first half with the reversed second half to see if we have a palindrome
3. When the hare reaches the end, the tortoise will be at the middle


 */
const checkPalindrome = (linkedlist) => {
  let slow = linkedlist.head
  let fast = linkedlist.head
  let firstHalfHead = linkedlist.head

  // Find middle
  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
  }

  // Reverse the second half
  secondHalfHead = reverse(slow)

  // Compare the first and second half
  while (firstHalfHead !== null && secondHalfHead !== null) {
    if (firstHalfHead.value !== secondHalfHead.value) {
      break // Not a palindrome
    }

    firstHalfHead = firstHalfHead.next
    secondHalfHead = secondHalfHead.next
  }

  // If both halves match
  if (firstHalfHead === null || secondHalfHead === null) {
    return true
  }

  return false
}

// Reverse Function
const reverse = (head) => {
  let previous = null
  while (head !== null) {
    next = head.next
    head.next = previous
    previous = head
    head = next
  }
  return previous
}