回文链表（234）

题目

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

示例

输入: 1->2 输出: false

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

算法

数组 + 双指针

将链表中的所有数字放在数组中，然后使用双指针从数组首尾开始检查是否是回文

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const isPalindrome = (head) => {
	const arr = [];
	while (head) {
		arr.push(head.val);
		head = head.next;
	}
	let l = 0,
		r = arr.length - 1;
	while (l < r) {
		if (arr[l] !== arr[r]) return false;
		l++;
		r--;
	}
	return true;
};

快慢指针 + 反转字符串

先使用快慢指针找到链表终点halfHead，然后使用递归的方法反转halfHead后面的链表

指向链表头部的指针listHead和指向链表中间且其后反转的指针halfHead，同时移动两个指针，如果遇到不同的值则返回false，比较到halfHead指向链表结尾则返回true

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const isPalindrome = (head) => {
	let fast = head,
		slow = head;
	listHead = head;
	while (fast && fast.next) {
		fast = fast.next.next;
		slow = slow.next;
	}
	function recursion(node) {
		if (!node || !node.next) return node;
		let head = recursion(node.next);
		node.next.next = node;
		node.next = null;
		return head;
	}
	let halfHead = recursion(slow);
	while (halfHead) {
		if (halfHead.val !== listHead.val) return false;
		halfHead = halfHead.next;
		listHead = listHead.next;
	}
	return true;
};