链表 - 234. 回文链表 - 《数据结构与算法》

题目
思路分析

题目

题目来源：力扣（LeetCode）

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

思路分析

双指针法

首先，遍历链表将节点值存储到数组列表中。我们使用 currentNode 指向当前节点，每次迭代时向数组添加 currentNode.val，并更新 currentNode = currentNode.next ，当 currentNode.next 为 null 时链表循环结束。

然后定义两个指针，prev 指针指向数组列表的起点位置，last 指针指向数组列表的结尾位置，遍历数组，每次迭代时判断两个指向指向的元素是否相同，若不同，则返回 false；若相同，则将两个指针同时向内移动，并继续判断，直到两个指针相遇。

/**
 * 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) {
  const vals = [];
  // 遍历链表，将链表的节点值存储到数组列表中
  while (head !== null) {
    vals.push(head.val);
    head = head.next;
  }
  // 定义两个指针，分别指向数组列表的起点位置和结尾位置
  // 每一次迭代判断两个指针指向的元素是否相同
  // 若不同，返回 false；相同则将两个指针向内移动，并继续判断，直到两个指针相遇
  for (let prev = 0, last = vals.length - 1; prev < last; ++prev, --last) {
    if (vals[prev] !== vals[last]) {
      return false;
    }
  }
  return true;
};

递归

使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

首先递归链表节点，直到指针 currentNode 指向尾节点，由于递归的特性，会再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。

let frontPointer;
const recursivelyCheck = (currentNode) => {
    if (currentNode !== null) {
        if (!recursivelyCheck(currentNode.next)) {
            return false;
        }
        if (currentNode.val !== frontPointer.val) {
            return false;
        }
        frontPointer = frontPointer.next;
    }
    return true;
}
var isPalindrome = function(head) {
    frontPointer = head;
    return recursivelyCheck(head);
};

快慢指针 + 反转后半部分链表

我们可以通过快慢指针找到链表的中间节点，然后以中间节点将链表分为前后两个部分，将后半部分链表反转，然后比较前半部分链表和后半部分链表，比较完成后将链表恢复原样。

具体步骤：

通过快慢指针找到链表的中间节点
以中间节点将链表分割为前后两部分链表
反转后半部分链表
比较前后两部分链表，判断是否回文
恢复链表
返回结果

在步骤1 中，使用快慢指针在一次遍历中找到链表的中间，快指针每次走两步，慢指针每次走一步，快慢指针同时出发，当快指针走到链表的末尾时，慢指针恰好走到链表的中间。我们以慢指针所指向的节点作为分割点，将链表分割为前后两个部分。

步骤2 中以链表中间节点分割链表时，由于是以中间节点作为分割点，若链表有奇数个节点，那么中间的节点应该开作是前半部分链表的节点。

分割完链表后，我们需要将后部分链表反转。

在步骤4 中，按照后半部分链表的长度，比较前后两部分链表的节点值是否相等，当后半部分链表到达末尾时，比较完成，可以忽略前半部分链表的尾节点，即原链表的中间节点。

比较完成后，需要将后半部分链表进行恢复，我们通常不希望链表结构被更改。

234. 回文链表 - 图3

代码：

/**
 * 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}
 */
// 反转链表
const reverseList = (head) => {
  let prev = null;
  let curr = head;
  while (curr !== null) {
      let nextTemp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = nextTemp;
  }
  return prev;
}
// 找到前半部分链表的尾节点
const endOfFirstHalf = (head) => {
  let fast = head; // 慢指针
  let slow = head; // 快指针
  // 快指针走两步，慢指针走一步，当快指针走到链表的末尾时，慢指针恰好到达链表的中间，然后通过慢指针将链表分为两部分
  while (fast.next !== null && fast.next.next !== null) {
      fast = fast.next.next;
      slow = slow.next;
  }
  return slow;
}
var isPalindrome = function(head) {
  if (head == null) return true;
  // 找到前半部分链表的尾节点
  const firstHalfEnd = endOfFirstHalf(head);
  // 反转后半部分链表
  const secondHalfStart = reverseList(firstHalfEnd.next);
  // 判断是否回文
  // 前半部分链表头节点
  let p1 = head;
  // 后半部分链表头节点
  let p2 = secondHalfStart;
  // result 默认为 true
  let result = true;
  // 原链表总长度如果是奇数，那么前半部分链表比后半部分链表多一个节点
  // 按照后半部分链表的长度，比较前半部分链表和后半部分链表的节点值是否相等
  while (result && p2 != null) {
    // 前半部分的链表的节点值与后半部分链表的节点值不相等，说明不是回文链表，返回 false
      if (p1.val != p2.val) result = false;
      p1 = p1.next;
      p2 = p2.next;
  }        
  // 还原链表并返回结果
  firstHalfEnd.next = reverseList(secondHalfStart);
  return result;
};

参考阅读 https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/ https://leetcode-cn.com/problems/palindrome-linked-list/solution/dai-ma-sui-xiang-lu-234-hui-wen-lian-bia-qs0k/