力扣 234. 回文链表

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

示例 1：

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

示例 2：

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

提示：

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

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

解

两种解法

• 将链表值存储到数组中，数组双指针判断
• 找到链表中间结点（快慢指针），反转链表后半段(迭代)，然后比较

数组双指针

• 时间复杂度 O(n)
• 空间复杂度 O(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 list = [];while(head != null) {list.push(head.val);head = head.next;}for(let i = 0, j = list.length - 1; i <= j; i++, j--) {if(list[i] != list[j])return false;}return true;
};

反转后半段链表比较

• 时间复杂度 O(n)
• 空间复杂度 O(1)

这个解法我感觉挺好的，主要就是有两个点吧：

找到中间结点：快慢指针，快指针每次跳两个结点， 慢指针一次跳一个结点，注意兼容链表奇偶个数

反转链表：考虑到性能优化， 用迭代算法反转以减小空间复杂度

/*** 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 reverseList = function(head) {// 迭代反转链表if(head == null || head.next == null) {return head;}let pre = null, cur = head;while(cur != null) {let next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;
}var midNode = function(head) {let front = head;let slow = head;while(front.next != null && front.next.next != null) {front = front.next.next;slow = slow.next;}return slow;
}var isPalindrome = function(head) {// 快慢指针确定中间结点，反转后半段链表比较if(head.next == null) {return true;}let mid = midNode(head);let endlist = reverseList(mid.next);let n = head;let scendn = endlist;while(scendn != null) {if(n.val != scendn.val) {return false;}scendn = scendn.next;n = n.next;}return true;
};

仅供参考，欢迎交流学习