LeetCode笔记：回文链表

#leetcode

问题

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

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

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

解法

思路：

  1. 先将链表转化为一个数组，再判断此数组是否为回文数组
  2. 循环这个数组，判断从开始和结束位置移动相同距离后的数值是否相同，全部相同则结果是为回文链表，有任何一组数值不同，则不是回文链表

代码：

/**
 * 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 transformList = [];
  // 存储当前节点
  let currentNode = head;

  // 每个节点的值存储到数组中
  while (currentNode != null) {
    transformList.push(currentNode.val);
    currentNode = currentNode.next;
  }

  // 循环到一半位置即可
  for (let i = 0; i < (transformList.length - 1) / 2; i++) {
    // 对比前后同样位置的数值，有任何一对数值不同即不是回文数组
    if (transformList[i] !== transformList[transformList.length - i - 1]) {
      return false;
    }
  }

  return true;
};

参考

评论