Determine if a linked list is palindromic.

Example 1:

Input:1->2Output:false
Copy the code

Example 2:

Input:1->2->2->1Output:true
Copy the code

Advanced: Can you solve this problem with O(n) time complexity and O(1) space complexity?

Their thinking

The official answer key

Method 1: fast and slow pointer

  1. Find the center node of the list by using the fast and slow Pointers
  2. Reverse the second half of the list
  3. Determine whether the linked list is palindrome
  4. Restore the second half of the list
  5. Returns the result

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {boolean}* /
var isPalindrome = function (head) {
  if(! head)return true;
  / /? 1. Find the center of the list by using the fast or slow pointer
  const endOfFirstHalf = head= > {
    let fast = head;
    let slow = head;
    while (fast.next && fast.next.next) {
      fast = fast.next.next;
      slow = slow.next;
    }
    return slow;
  };
  / /? 2. Reverse the second half of the list
  const reverseList = head= > {
    let pre = null;
    let cur = head;
    while (cur) {
      let next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  };
  let firstHalfEnd = endOfFirstHalf(head);
  let secondHalfStart = reverseList(firstHalfEnd.next);
  // 3. Check whether the linked list is palindrome
  let p1 = head;
  let p2 = secondHalfStart;
  let result = true;
  while(p2 ! = =null && result) {
    if(p1.val ! == p2.val) { result =false;
    }
    p1 = p1.next;
    p2 = p2.next;
  }
  // 4. Restore the second half of the list
  firstHalfEnd.next = reverseList(secondHalfStart);
  return result;
};

Copy the code