力扣 234. 回文链表

力扣 234. 回文链表

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

反转后半段链表比较

• 时间复杂度 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;
};
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
50
51
52
53
54
55

仅供参考，欢迎交流学习