判断链表是否是回文链表

Example 1:

1 2	Input: 1 → 2 Output: false

Example 2:

1 2	Input: 1 → 2 → 2 → 1 Output: true

Follow up:
Could you do it in O(n) time and O(1) space?
(Try to solve this problem in O(N) time and O(1) space. Hint: Reverse part of the linked list.)

1.反转部分链表

const isPalindrome = function(head) {
  if(!head || !head.next){
    return true;
  }
  if(!head.next.next){
    return head.val === head.next.val;
  }
  let slow = head;
  let fast = head;
  while(fast.next && fast.next.next){
    slow = slow.next;
    fast = fast.next.next;
  }
  slow.next = reverseList(slow.next);
  fast = head;
  slow = slow.next;

  while(slow !== null){
    if(fast.val !== slow.val){
      return false;
    }
    else{
      fast = fast.next;
      slow = slow.next;
    }
  }
  return true;
};

const reverseList = function(head) {
  let prev = null;
  let save = null;
  while(head){
    save = head.next;
    head.next = prev;
    prev = head;
    head = save;
  }
  return prev;
};

2.使用堆

const isPalindrome = function(head) {
  if(head === null) {
    return true;
  }

  const stack = [];
  let temp = head;

  while(head != null) {
    stack.push(head.val);
    head = head.next;
  }

  while(temp != null) {
    if (temp.val != stack.pop()) {
      return false;
    }
    temp = temp.next;
  }
  return true;
};

3.使用递归

const isPalindrome = function(head) {
  return recurse(head);

  function recurse(node){
    if (node === null){
      return true;
    }

    const isPal = recurse(node.next);

    if(node.val === head.val){
      head = head.next;
      return isPal;
    }
    else{
      return false;
    }
  }
};

4.让链表变成双向的

const isPalindrome = function(head) {
  if(!head){
    return true;
  }

  let index = head;
  index.prev = null;

  while(index.next){
    index.next.prev = inedx;
    index = index.next;
  }

  while(index !== head){
    if(index.val === head.val){
      index = index.prev;
      head = head.next
    }
    else{
      return false;
    }
  }
  return true;
};

Palindrome Linked List

判断链表是否是回文链表