234. Palindrome Linked List

Problem

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up: Could you do it in O(n) time and O(1) space?

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  var left = null;
  var right = null;
  var slow = head;
  var fast = head;
  var tmp = null;

  while (fast && fast.next) {
    fast = fast.next.next;
    tmp = slow.next;
    slow.next = left;
    left = slow;
    slow = tmp;
  }
  right = fast ? slow.next : slow;

  while (left && right) {
    if (left.val !== right.val) return false;
    left = left.next;
    right = right.next;
  }

  return true;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).