Pengjielee's blog

题目

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

示例 1:
输入: 1->2
输出: false

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

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/palindrome-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、将值复制到数组中后用双指针法

/**
 * 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 values = [];
  // 将链表的值保存到数组中
  while (head != null) {
    values.push(head.val);
    head = head.next;
  }
  // 使用快慢指针，一个指向数组头，一个指向数组尾
  for (let i = 0, j = values.length - 1; i < j; i++, j--) {
    // 判断头尾元素的值是否相等，不相等直接返回false
    if (values[i] != values[j]) {
      return false;
    }
  }
  return true;
};

2、

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

  // 反转链表
  const reverseList = (head) => {
    // 前继节点
    let prev = null;
    // 当前节点
    let curr = head;
    while (curr != null) {
      // 下个节点
      let temp = curr.next;
      // 下个节点指向prev，完成反转
      curr.next = prev;
      // prev指向curr
      prev = curr;
      // curr向右移
      curr = temp;
    }
    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;
  };

  // 前半部分的结尾
  const firstHalfEnd = endOfFirstHalf(head);
  // 对后半部分链表进行反转，获取其开始结点
  const secondHalfStart = reverseList(firstHalfEnd.next);

  let p1 = head;
  let p2 = secondHalfStart;
  let result = true;

  while (result && p2 != null) {
    if (p1.val != p2.val) {
      result = false;
    }
    p1 = p1.next;
    p2 = p2.next;
  }

  // 还原后半部分链表
  firstHalfEnd.next = reverseList(secondHalfStart);
  return result;
};

测试数据：

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}
var node1 = new ListNode(1);
var node2 = new ListNode(2);
var node3 = new ListNode(2);
var node4 = new ListNode(1);
node1.next = node2;
node2.next = node3;
node3.next = node4;