解题思路

快慢指针 + 反转链表

1. 使用快慢指针找到链表的中点。
2. 反转后半部分链表。
3. 比较前半部分和反转后的后半部分是否相等。
4. 恢复链表（可选）。
5. 时间复杂度：( O(n) )，空间复杂度：( O(1) )。

代码实现

C++ 版本

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}

// 判断是否是回文链表
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;

    // 快慢指针找到中点
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 反转后半部分链表
    ListNode* secondHalf = reverseList(slow);
    ListNode* firstHalf = head;
    ListNode* temp = secondHalf;
    bool isPalin = true;

    // 比较前半部分和后半部分
    while (temp) {
        if (firstHalf->val != temp->val) {
            isPalin = false;
            break;
        }
        firstHalf = firstHalf->next;
        temp = temp->next;
    }

    // 恢复链表（可选）
    reverseList(secondHalf);

    return isPalin;
}

int main() {
    int n;
    cin >> n;
    ListNode* head = nullptr, *tail = nullptr;
    
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        ListNode* newNode = new ListNode(val);
        if (!head) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    cout << (isPalindrome(head) ? "true" : "false") << endl;
    return 0;
}

Python 版本

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

# 反转链表
def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

# 判断是否是回文链表
def is_palindrome(head):
    if not head or not head.next:
        return True

    # 快慢指针找到中点
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 反转后半部分链表
    second_half = reverse_list(slow)
    first_half, temp = head, second_half
    is_palin = True

    # 比较前半部分和后半部分
    while temp:
        if first_half.val != temp.val:
            is_palin = False
            break
        first_half = first_half.next
        temp = temp.next

    # 恢复链表（可选）
    reverse_list(second_half)

    return is_palin

# 处理输入
if __name__ == "__main__":
    n = int(input().strip())
    values = list(map(int, input().split()))

    # 构建链表
    head = ListNode(values[0])
    curr = head
    for val in values[1:]:
        curr.next = ListNode(val)
        curr = curr.next

    print("true" if is_palindrome(head) else "false")

Java 版本

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Main {
    // 反转链表
    private static ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }

    // 判断是否是回文链表
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // 快慢指针找到中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转后半部分链表
        ListNode secondHalf = reverseList(slow);

        // 比较前半部分和后半部分
        ListNode firstHalf = head, temp = secondHalf;
        boolean isPalin = true;
        while (temp != null) {
            if (firstHalf.val != temp.val) {
                isPalin = false;
                break;
            }
            firstHalf = firstHalf.next;
            temp = temp.next;
        }

        // 恢复链表（可选）
        reverseList(secondHalf);

        return isPalin;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ListNode head = null, tail = null;

        for (int i = 0; i < n; i++) {
            int val = scanner.nextInt();
            ListNode newNode = new ListNode(val);
            if (head == null) {
                head = tail = newNode;
            } else {
                tail.next = newNode;
                tail = newNode;
            }
        }
        scanner.close();

        System.out.println(isPalindrome(head) ? "true" : "false");
    }
}

题目描述

给定一个 单链表，其节点由一个整数值表示，请判断该链表是否为 回文链表。
如果是，返回 true；否则，返回 false。

输入格式

• 第一行输入一个整数 n，表示链表的 节点数。（1 ≤ n ≤ 10⁵）
• 第二行输入 n 个整数，表示链表的值。（0 ≤ Node.val ≤ 9）

输出格式

• 输出 true 或 false，表示链表是否为回文链表。

样例 1

输入

4
1 2 2 1

解释：

链表结构：1 → 2 → 2 → 1

输出

true

样例 2

输入

2
1 2

解释：

链表结构：1 → 2

输出

false

数据范围

• $1 \leq n \leq 10^5$

• $0 \leq \text{Node.val} \leq 9$