234. 回文链表

1. 题目描述

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

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

2. 解题思路

字符串拼接：
对于这道题，最直接的思路就是，遍历链表，同时正向和反向拼接链表的节点，最后比较两个拼接出来的字符串是否一样。

这种方式的时间复杂度为O(n)，空间复杂度为O(1)

递归遍历：

• 首先，定义一个全局的指针pointer，其初始值为head，用来正序遍历
• 然后，调用递归函数，对链表进行逆序遍历，当头部节点为null的时候停止遍历
• 如果正序遍历的节点值和逆序遍历的节点值都相等，就返回true，否则就返回false

这种方式的时间复杂度为O(n)，空间复杂度为O(1)

3. 代码实现

字符串拼接：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let a = ""
    let b = ""
    while(head){
        const nodeVal = head.val
        a = a + nodeVal
        b = nodeVal + b
        head = head.next
    }
    return a === b
};

递归遍历：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
let pointer
function fn(head) {
    if(!head) return true
    const res = fn(head.next) && (pointer.val === head.val)
    pointer = pointer.next
    return res
} 
var isPalindrome = function(head) {
    pointer = head
    return fn(head)
};

4. 提交结果

字符串拼接：

递归遍历：