234.回文链表.md

LeetCode 234.回文链表

描述

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶：

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

题解

方法一

思路

暴力解法：

1. 遍历整个链表
2. 使用数组存储每个节点值
3. 获取中点截取后转字符串进行比较

代码

var isPalindrome = function(head) {
    var arr = [];
    while(head){
        arr.push(head.val);
        head = head.next;
    }
    var len = arr.length;
    if(len < 2){
        return true;
    }
    var index = len % 2 === 0? len/2:len/2+1;
    return arr.slice(0,len/2).reverse().join("") === arr.slice(index).join("");; 
};

方法二

思路

快慢指针解法：

1. 定义快指针fast, 慢指针slow 移动次数比 fast=>2 slow=>1
2. 快指针fast到达终点后此时慢指针slow刚好在中点
3. 遍历同时反转前一部分链表与后半部分链表循环判断不同直接返回false都相同则返回true

代码

var isPalindrome = function(head) {
   if(head === null || head.next === null)  return true;
   let fast = head.next, slow = head, pre = null, prepre = null;
   while(fast!=null && fast.next != null) {
       pre = slow;
       slow = slow.next;
       fast = fast.next.next;
       pre.next = prepre;
       prepre = pre;
    }
    var second = slow.next;
    slow.next = pre;
    var first = !fast?slow.next:slow;
    while(first){
        if(first.val !== second.val){
            return false
        }
        first = first.next;
        second = second.next;
    }
    return true;
};

// eg:1-->2-->2-->1