给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围[1, 10^5] 内
- 0 <= Node.val <= 9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
先找到链表中间，再将另一半链表反转。比如找到中间 [1,2(mid),2,1] ，将链表反转后[1(first),2,1(second),2] ，然后迭代比较 first 和 second 即可。
- 可使用快慢指针找到 mid ：慢指针每次移动一次，快指针每次移动两次。
- 可使用多指针反转链表（参见 leetcode 206）。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head: return False
mid_node = self.find_mid_position(head)
second_start = self.reverse_link_node(mid_node.next)
second_node = second_start
first_node = head
res = True
while res and second_node:
if second_node.val != first_node.val:
res = False
second_node = second_node.next
first_node = first_node.next
# 最后恢复链表
mid_node.next = self.reverse_link_node(second_start)
return res
def find_mid_position(self, head):
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse_link_node(self, node):
pre = None
cur = node
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
- 时间复杂度 O(n) ：n 为链表长度。
- 空间复杂度 O(1)。