回文链表

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

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

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

方法一：遍历+检索

思路：核心思路是把单链表存储出来，然后进行回文数的判断即可。

# 遍历+检索
# 核心思路是把单链表存储出来，然后进行回文数的判断即可。
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        ans = []
        while head:
            ans.append(head.val)
            head = head.next
        return ans == ans[::-1]

方法二：递归

思路：指向头尾两个节点，然后依次判断即可。

# 递归
# 指向头尾两个节点，然后依次判断即可。
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        self.front_pointer = head
        def recursively_check(current_node = head):
            if current_node is not None:
                if not recursively_check(current_node.next):
                    return False
                if self.front_pointer.val != current_node.val:
                    return False
                self.front_pointer = self.front_pointer.next
            return True
        return recursively_check()

方法三：反转链表

思路：此算法比较难想，核心在于找到尾节点并反转链表进行判断，然后恢复原有链表，返回即可。

# 反转链表
# 此算法比较难想，核心在于找到尾节点并反转链表进行判断，然后恢复原有链表，返回即可。
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return True
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next
        first_half_end.next = self.reverse_list(second_half_start)
        return result    
    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow
    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous

总结

这真的是简单吗？