一起学习LeetCode热题100道（24/100）

24.回文链表(学习)

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

示例 1：

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

示例 2：

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

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

解析：
一、找到链表的中点
1.初始化两个指针 slow 和 fast，都指向链表的头节点 head。
2.进入循环，条件为 fast 和 fast.next 都不为 null（确保 fast 可以安全地移动两步）。
3.在循环内部，slow 指针每次向前移动一步（slow = slow.next），fast 指针每次向前移动两步（fast = fast.next.next）。
4.当循环结束时，slow 指针要么指向链表的中点（如果链表长度是偶数），要么指向中间两个节点的第一个（如果链表长度是奇数）。

二、反转链表的后半部分
1.从 slow 指针开始反转链表。注意，如果链表长度是奇数，我们实际上是从 slow.next 开始反转的，因为 slow 已经是指向中间节点的指针了。
2.使用三个指针 prev（初始化为 null），curr（初始化为 slow 或 slow.next，取决于链表长度是否为奇数），和 nextTemp 来反转链表。
3.在循环中，将 curr.next 保存到 nextTemp，然后将 curr.next 指向 prev，接着将 prev 向前移动到 curr，最后将 curr 向前移动到 nextTemp。
4.循环继续，直到 curr 为 null。此时，prev 就是反转后的链表的头节点。

三、比较前半部分和反转后的后半部分
1.初始化两个指针 p1 和 p2，分别指向原链表的头节点 head 和反转后的链表的头节点 prev。
2.进入循环，条件为 p2 不为 null（确保我们可以安全地遍历反转后的链表的后半部分）。
3.在循环内部，比较 p1.val 和 p2.val。如果它们不相等，则返回 false，因为链表不是回文的。
4.如果它们相等，则将 p1 和 p2 都向前移动一步（p1 = p1.next 和 p2 = p2.next）。
5.循环结束后，如果没有提前返回 false，则说明链表是回文的，返回 true。

var isPalindrome = function(head) {
     if (!head || !head.next) return true;  
  
    let slow = head;  
    let fast = head;  
    let prevPtr = null;  
  
    // 使用快慢指针找到中点  
    while (fast && fast.next) {  
        prevPtr = slow;  
        slow = slow.next;  
        fast = fast.next.next;  
    }  
  
    // 如果链表长度为奇数，则跳过中点  
    if (fast) {  
        slow = slow.next;  
    }  
  
    // 反转链表的后半部分  
    let secondHalf = reverseList(slow);  
  
    // 比较前半部分和反转后的后半部分  
    let p1 = head;  
    let p2 = secondHalf;  
    while (p2) {  
        if (p1.val !== p2.val) {  
            return false;  
        }  
        p1 = p1.next;  
        p2 = p2.next;  
    }  
  
    // 如果需要，可以在这里恢复链表（可选）  
  
    return true; 
};

function reverseList(head) {  
    let prev = null;  
    let curr = head;  
    while (curr) {  
        let nextTemp = curr.next;  
        curr.next = prev;  
        prev = curr;  
        curr = nextTemp;  
    }  
    return prev; // 新的头节点  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49