1
/**
2
 * Definition for singly-linked list.
3
 * function ListNode(val, next) {
4
 * this.val = (val===undefined ? 0 : val)
5
 * this.next = (next===undefined ? null : next)
6
 * }
7
 */
8
/**
9
 * @param {ListNode} head
10
 * @return {boolean}
11
 */
12
var isPalindrome = function (head) {
13
  let slow = head;
14
  let fast = head;
15
  // Moving slow one step at a time while fast, two steps
16
  while (fast && fast.next) {
17
    slow = slow.next;
18
    fast = fast.next.next;
19
  }
20
  // This way, slow will end up right after the middle node
21
  // Reverse the list from that node
22
  slow = reverse(slow);
23
  fast = head;
24
  // Now check for equality first half and second half of the list
25
  while (slow) {
26
    if (slow.val !== fast.val) {
27
      return false;
28
    }
29
    slow = slow.next;
30
    fast = fast.next;
31
  }
32
  return true;
33
};
34

35
// Function to reverse a LinkedList
36
function reverse(head) {
37
  let prev = null;
38
  while (head) {
39
    let nextNode = head.next;
40
    head.next = prev;
41
    prev = head;
42
    head = nextNode;
43
  }
44
  return prev;
45
}