234_回文链表

类型：链表

• 234. 回文链表 💚

  https://leetcode-cn.com/problems/palindrome-linked-list/

  ❓ 判断一个链表是否为回文链表（如 1->2->2->1）。

  💡 递归

  使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

  class Solution:
      def isPalindrome(self, head: 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()

  时间复杂度：O(n)，空间复杂度：O(n)

  💡 后半部分反转

  反转后半部分链表，然后再判断回文。

  class Solution:
      def isPalindrome(self, head: ListNode) -> bool:
          if not head or not head.next:
              return True
          preNode = None
          slowNode = head
          fastNode = head
          while fastNode is not None and fastNode.next is not None:
              fastNode = fastNode.next.next
              tempNode = slowNode.next
              slowNode.next = preNode
              preNode = slowNode
              slowNode = tempNode
          if fastNode:
              slowNode = slowNode.next
          while preNode:
              if preNode.val != slowNode.val:
                  return False
              else:
                  preNode = preNode.next
                  slowNode = slowNode.next
          return True

  时间复杂度：O(n)，空间复杂度：O(1)