回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
codeType
输入：head = [1,2,2,1]
输出：true
示例 2：
codeType
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围[1, 105] 内
- 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解法
解法一：辅助栈
ts
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function isPalindrome(head: ListNode | null): boolean {
// 因为是单链表，不好用双指针解决
// 可以用栈解决，但是需要O(n)的空间复杂度
const stack = []
let p = head
while(p !== null){
stack.push(p)
p = p.next
}
p = head
const len = stack.length
for(let i = 0; i < Math.floor(len / 2); i++){
if(p.val !== stack.pop().val){
return false
}
p = p.next
}
return true
};
解法二
解一需要O(n)的空间复杂度。我们可以将链表的后半部分进行反转，然后逐个比较，最后再反转回去。
ts
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
// 反转链表
const reverseList = (head) => {
let prev = null;
let curr = head;
while (curr !== null) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// 找到链表一半的位置
const endOfFirstHalf = (head) => {
let fast = head;
let slow = head;
while (fast.next !== null && fast.next.next !== null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
function isPalindrome(head: ListNode | null): boolean {
if (head == null) return true;
// 找到前半部分链表的尾节点并反转后半部分链表
const firstHalfEnd = endOfFirstHalf(head);
const secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
let p1 = head;
let p2 = secondHalfStart;
let result = true;
while (result && p2 != null) {
if (p1.val != p2.val) result = false;
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
};