一. 题目

二. 思路

• 将前半部分或后半部分链表翻转，然后两个指针遍历，即可时间O(n)，空间O(1)。

三. 代码

class ListNode
{
    int val;
    ListNode next;

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

class Solution
{
    public boolean isPalindrome(ListNode head)
    {
        int n = 0;
        ListNode ph = head, pt;
        while (ph != null)//统计节点数
        {
            ++n;
            ph = ph.next;
        }
        if (n == 1) return true;//一个节点一定是回文

        int cnt = n % 2 == 0 ? n / 2 : n / 2 + 1;//分割节点位置
        ListNode pl = null, pr = null;//前一个节点和后一个节点
        ph = head;
        for (int i = 0; i < cnt; ++i)//将回文串前半部分翻转
        {
            pr = ph.next;
            ph.next = pl;
            pl = ph;
            ph = pr;
        }

        pt = pr;//让指针指向判断的前后起始位置
        if (n % 2 == 0) ph = pl;
        else ph = pl.next;
        boolean ans = true;
        while (ph != null)//开始判断
        {
            if (ph.val != pt.val)
            {
                ans = false;
                break;
            }
            ph = ph.next;
            pt = pt.next;
        }
        return ans;
    }
}