回文的特点

先从回文数说起，
回文数的特点：以中轴对称
1、以中轴对称
2、回文数正读和反着读都是一样的

判断一个字符串是不是回文串就简单很多，不需要考虑奇偶情况，只需要「双指针技巧」，从两端向中间逼近即可。

function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] != s[right])
            return false;
        left++; right--;
    }
    return true;
}

从中轴对称角度出发，可将双指针优化为一个指针,j=len-1-i,while(i

申请额外空间

而判断单链表是否为回文，难度主要在：单链表一开始就定位到链尾，且从链尾开始倒着遍历
所以解决方案：
way1、找一个可以反着遍历的容器：遍历一次链表，然后将链表的值放入申请的额外空间如数组里，进而转换为数组的回文判断
way2、利用正读和倒读是一样的特点，将链表反转生成新链表，然后同时遍历原链表和反转后的链表

# way1 额外空间-数组
function isPalindrome(head) {
    let arr = [];
    while (head) {
        arr.push(head.val);
        head = head.next;
    }
    let i=0;
    let len=arr.length;
    while (i<=Math.floor(len/2)) {
        if (arr[i] !== arr[len-1-i]) {
            return false;
        }
        i++;
    }
    return true;
}
# way2 额外空间-反转整个链表
function isPalindrome(head) {
    let reverseDummy = new ListNode();
    let p = head;
    while(p) {
        let next_temp = p.next;
        p.next = reverseDummy.next;
        reverseDummy.next = p;
        p = next_temp;
    }
    console.log(reverseDummy) // 新的反转的节点
    console.log(head) // head节点被破坏了断链了 =》因为是引用修改 => 解决方式1.p= 深拷贝(head)
    // 有没有其他方式：能在反转链表后 保持head节点指向原链表的头节点 
    let reverseHead = reverseDummy.next;
    while(reverseHead && head) {
        if (reverseHead.val !== head.val) {
            return false;
        }
        reverseHead = reverseHead.next;
        head = head.next;
    }
    return true;
}

递归解决

然后我们试试从递归的角度解决这个问题：

借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表
二叉树遍历方式推导出链表的前后序遍历方式

# 二叉树
function traverse(root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
}

# 单链表
function traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}

# way3 递归
function isPalindrome(head) {
    let left = head;
    return traverse(head);

    function traverse(node) {
        if (node==null) return true;
        let prevIsSame = traverse(node.next);
        // 逆序输出code
        let currIsSame = left.val === node.val;
        left = left.next;// left通过这种方式向右，node通过弹栈的方式向左
        return prevIsSame && currIsSame;
    }
}

O(1)空间

不申请额外空间：
way3、不申请额外空间：遍历第一遍，将原链表构造成双向链表，保留链尾指针和链头指针，第二遍遍历的时候两指针向中间靠近

way4：使用快慢指针，找到链表的中间结点，将链表的右半边反转，然后head指针和tail指针分别向中间遍历

# way4 双向链表
function isPalindrome(head) {
    let tail = head
    let prev = null
    while(tail) {
        tail.prev = prev
        prev = tail
        tail = tail.next
    }
    // prev指向链尾
    let temp = prev
    while(head) {
        if (head.val === temp.val) {
            head = head.next
            temp = temp.prev
        } 
        else {
            return false
        }
    }
    return true
}

# way5 反转右半部分链表
function isPalindrome(head) {
    if (head==null || head.next ==null) return true;

    // 快慢指针找中间结点
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 当链表为偶数是，slow指向中轴偏左，链表为奇数，slow指向中间结点
    slow.next = reverse(slow.next); // 反转右半边链表
    // 1->2->3->2->1
    // 1->2->3->1->2
    // slow指向右半边链表的第一个结点,head还是链表的第一个结点
    slow = slow.next;

    // 两指针一起遍历判断
    while(slow) {
        if (slow.val !== head.val) {
            return false;
        }
        slow = slow.next;
        head = head.next;
    }
    return true;

    // 反转链表 返回新的头结点
    function reverse(head) {
        let prev = null;
        while(head) {
            let nex_temp = head.next;
            head.next = prev;
            prev = head;
            head = nex_temp;
        }
        return prev;
    }   
}

🤔数据结构与算法

回文链表

回文的特点

申请额外空间

递归解决

O(1)空间