234. 回文链表

🟢   🔖  栈 递归 链表 双指针  🔗 力扣 LeetCode

题目

Given the head of a singly linked list, return true if it is apalindrome orfalse otherwise.

Example 1:

Input: head = [1,2,2,1]

Output: true

Example 2:

Input: head = [1,2]

Output: false

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

题目大意

判断一个链表是否是回文链表。要求时间复杂度 O(n)，空间复杂度 O(1)。

解题思路

这道题只需要在 第 143 题 上面改改就可以了，思路是完全一致的。

• 先找到中间结点，然后反转中间结点后面到结尾的所有结点；
• 最后依次判断头结点开始的结点和中间结点往后开始的结点是否相等；
• 如果一直相等，就是回文链表，如果有不相等的，直接返回不是回文链表。

代码

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
	if (!head || !head.next) return true;

	// 找到中点
	let slow = head;
	let fast = head;
	while (fast.next && fast.next.next) {
		slow = slow.next;
		fast = fast.next.next;
	}

	// 从中间开始反转链表
	const middle = slow;
	let cur = middle.next;
	while (cur.next) {
		let temp = cur.next;
		cur.next = temp.next;
		temp.next = middle.next;
		middle.next = temp;
	}

	slow = head;
	fast = middle.next;
	while (fast) {
		if (slow.val == fast.val) {
			slow = slow.next;
			fast = fast.next;
		} else {
			return false;
		}
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度
9	回文数	[✓]	数学
125	验证回文串	[✓]	双指针 字符串
206	反转链表	[✓]	递归 链表
2130	链表最大孪生和		栈 链表 双指针