请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

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

Solution

• 借助数组记录节点，空间复杂度 O(n)

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) return false;
        vector<int> record;
        while (head) {
            record.push_back(head->val);
            head = head->next;
        }

        int l = 0, r = record.size()-1;
        while (l <= r) {
            if (record[l++] != record[r--])
                return false;
        }
        return true;
    }
};
// @lc code=end

参考：《算法小抄》3.9

• 借助递归栈，实现链表的后序遍历
• 模仿双指针实现回文判断的功能
• 空间复杂度 O(n)

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        self.left = head
        def traverse(right):
            if not right:
                return True
            res = traverse(right.next)
            res = res and (self.left.val == right.val)
            self.left = self.left.next
            return res
        
        return traverse(head)
# @lc code=end

优化空间复杂度

• 先通过「双指针技巧」中的快慢指针来找到链表的中点
• 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步
• 从slow开始反转后面的链表，现在就可以开始比较回文串了
• 最好最后在翻转回来

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        if fast:
            slow = slow.next
            
        def reverse(head):
            pre = None
            cur = head
            while cur:
                nex = cur.next
                cur.next = pre
                pre = cur
                cur = nex
            return pre
        
        left, right = head, reverse(slow)
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

cpp

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) return false;
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* head2 = reverse(slow);
        while (head2) {
            if (head->val != head2->val) {
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }
        return true;

    }
private:
    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};