原题

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

链表结构如下

    let l2 = {
      val: 1,

      next: {
        val: 2,

        next: {
          val: 4,

          next: null,
        },
      },
    };

解法1

我想了半天这玩意能不能用递归做出来，没想出来...
干脆正向遍历链表，把它的值存储起来，心里顿时就舒服了。
一开始的解法

var isPalindrome = function(head) {
    let right = head,list = [];
    
    while(right !== null){
        list.push(right.val);
        right = right.next; 
    }
    list = list.reverse();
    let i = 0;
    while(head !== null){
        if(head.val !== list[i++]){
            return false;
        }
        head = head.next; 
    }
    return true;

};

不知你发没发现里面的"蜜汁"操作
既然都用到了reverse方法，为啥还要和链表本身去比...

优化后的解法:

var isPalindrome = function(head) {
    let right = head,list = [];
    
    while(right !== null){
        list.push(right.val);
        right = right.next; 
    }
    
    let isFlag = list.join() === list.reverse().join();
    return isFlag;

};

然而看过其他大哥相同思路的不同解法后我还是颇为欣慰的!

种类1

var isPalindrome = function(head) {
  const deq = []
  let p = head
  while(p) {
    deq.push(p.val)
    p = p.next
  }
  
  const len = deq.length
  const mid = ~~(len / 2)
  let ans = true
  for (let i = 0; i < mid; i++) {
    if (deq[i] !== deq[len - 1 - i]) {
      ans = false
      break
    }
  }
  return ans
};

不忘初心啊！既然链表不能第一个和最后一个比较，我就转换为数组继续！

解法2

其实题目还有一个要求，你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题，就是只遍历一次链表，且不创造额外空间。
经验告诉我，这个时候一定要发现数的规律(我看完别人的答案才发现的)
我们以[1,2,1,2,1] 举例，前面的1 2 反转过来不就是后面的2 1 嘛

var isPalindrome = function(head) {
  if (head === null || head.next === null) return true;
  let last = head; //链表的后半段
  let pre = null;
  let reversed = null; //存储链表前面的反转

  while (head !== null && head.next !== null) {
    pre = last;

    last = last.next;
  
    head = head.next.next;
 
    pre.next = reversed;
    reversed = pre;
  }

  if (head) last = last.next;
  while (last) {
    if (reversed.val !== last.val) return false;
    reversed = reversed.next;
    last = last.next;
  }
  return true;
};

如果下面问题捋清楚了，后面的可以不用看了。

1. if (head) last = last.next; 在输入符合什么情况时会产生作用
2. 程序是如何完成反转的
3. 程序如何确保找到中间值后退出循环的

一本正经的解答