回文链表

回文链表指的是一个链表正着读和倒着读都是一样的，如 1->2->3->2->1 就是一个回文链表。

要判断一个链表是否为回文链表，可以使用双指针法。具体做法如下：

1. 找到链表的中点。可以使用快慢指针，慢指针每次移动一步，快指针每次移动两步，当快指针到达链表末尾时，慢指针就到达了中点。

2. 反转后半部分链表。从中点开始，反转后半部分链表。

3. 判断回文。将链表分成前半部分和后半部分，分别使用两个指针遍历比较即可。

下面是一个 Python 实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True

    # 找到链表的中点
    slow, fast = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

    # 反转后半部分链表
    prev, curr = None, slow
    while curr:
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp

    # 比较前半部分和后半部分
    p1, p2 = head, prev
    while p2:
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next

    return True

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表两次，时间复杂度是线性的。

空间复杂度：O(1)。只需要常数的额外空间。