234. 回文链表 (opens new window)

Description

Difficulty: 简单

Related Topics: 栈 (opens new window), 递归 (opens new window), 链表 (opens new window), 双指针 (opens new window)

给你一个单链表的头节点 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

双指针

首先将链表转为数组

左指针指向第一个节点

右指针指向最后一个节点

比较两个指针指向的节点中的数据

在两个指针相遇之前没有遇到不相等的节点则返回true

否则返回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) {
    if(head == null || head.next == null) {return true}
    let slow = head
    let fast = head
    let temp1 = null ,temp2 = null
    while(fast !=null && fast.next !=null){
        temp1 = slow
        slow = slow.next
        fast = fast.next.next

        temp1.next  = temp2
        temp2 = temp1
    }
    if(fast){
        slow = slow.next
    }

    while(slow){
        if(slow.val != temp2.val){return false}
        slow = slow.next 
        temp2 = temp2.next
    }
    return true


};


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;
};