234. 回文链表

[webVueBlog]

234. 回文链表

Description

Difficulty: 简单

Related Topics: 栈, 递归, 链表, 双指针

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[1, 10⁵] 内
• 0 <= Node.val <= 9

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

Solution

Language: JavaScript

/**
 * 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}
 */
// 双指针
// 首先将链表转为数组
// 左指针指向第一个节点
// 右指针指向最后一个节点
// 比较两个指针指向的节点中的数据
// 在两个指针相遇之前没有遇到不相等的节点则返回true，否则返回false
var isPalindrome = function(head) {
    let arr = [];
    while(head){
        arr.push(head.val);
        head = head.next;
    }
    let left = 0, right = arr.length-1;
    while(left <= right){
        if(arr[left] != arr[right]) return false;
        left++;
        right--;
    }
    return true;
};