算法：回文链表

234. 回文链表

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

示例 1：

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

示例 2：

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

提示：

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

我的解题思路

判断回文链表、回文数字、回文字符、回文数组等都可以直接将原参数反转然后二者再进行比较，如果一模一样的话，就是成功的

但是在链表中，我们无法直接比较两个链表，所以我们在这里把它转换成数组

*注：数组翻转会改变原有数组，所以本来是要进行深拷贝的，然后我们不能直接比较两个数组是否一样，所以需要将数组再转换成文字，所以也就不用深拷贝了

/**
 * 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) {
    let arr = [];
    while (head) {
        arr.push(head.val) // 将链表节点写进数组
        head = head.next // 移动链表节点
    }
    if (arr.toString() === arr.reverse().toString()) {
        return true 
    } else {
        return false
    }
};

但是我们这个空间复杂度是真的高啊……然后发现官方的解决办法也是挺简单的……

官方思路

也是先将链表复制到数组中，然后用双指针法

确定数组列表是否回文很简单，我们使用双指针法来比较两端的元素，一个从前到后为头指针，一个从后向到前为尾指针，并一起向中间移动

复杂度分析

• 时间复杂度

  1.将链表复制到数组中，这需要O（n）的时间，因为访问一个元素是O(1),一共有n个元素。

1. 判断是否为回文，执行了O(n/2)次判断，即O(n)
   所以总的时间复杂度O(2n)=O(n)

• 空间复杂度
  O(n)，n是链表元素个数

/**
 * 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) {
    let arr = []
    while (head) {// 循环条件为只要元素存在
        arr.push(head.val) // 将当前节点值写入数组中，注意是head.val不是head哦
        head = head.next // 移动指针
    }
    let i = 0, j = arr.length - 1; // 定义两个指针，一个从头开始，一个从尾开始
    while(i < j ) { // 两指针一起向中间移动，所以条件为i<j，比较次数为n/2
        if (arr[i] !== arr[j]) { // 首尾两元素不相等代表不是回文
            return false;
        }
        i++; // 移动头指针
        j--; // 移动尾指针
    }
    return true;
    
};