请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list

AC代码

/**
 * 思路：使用快慢指针，快指针速度为慢指针2倍，快指针走到终点时，慢指针走到中点
 * 以1->2->3->2->1为例，快指针走到终点时，慢指针走到3
 * 慢指针走到中点这一过程中，把慢指针走过的部分反转链表
 * 也就是整个链表被分成1<-2<-3, 3->2->1两个子链表
 * 遍历这两个子链表，判断是否回文
 */
public boolean isPalindrome(ListNode head) {
    if (head == null) {
        return true;
    }

    // 定义快慢指针，快指针速度为慢指针2倍
    ListNode slow = head, fast = head;
    // 链表总节点数
    int count = 1;
    // 用于反转链表，last表示slow的上个节点，lastLast表示slow的上上个节点
    ListNode last = null, lastLast = null;

    while (true) {
        fast = fast.next;
        // 走奇数步后为null，说明节点总数是奇数
        if (fast == null) {
            break;
        }
        count ++;

        fast = fast.next;
        // 走偶数步后为null，说明节点总数是偶数
        if (fast == null) {
            break;
        }
        count ++;

        // 把slow走过的部分反转链表
        lastLast = last;
        last = slow;
        slow = slow.next;
        // 把根节点的next设为null
        if (count == 1) {
            last.next = null;
        }
        // last.next设为lastLast
        if (last != null && lastLast != null) {
            last.next = lastLast;
        }
    }

    // while循环退出后，slow指向中间节点，slow的next还未指向last
    // 假设链表共n个节点，编号从1开始
    // 如果n是偶数，slow指向n/2，把fast指向n/2+1
    if (count % 2 == 0) {
        fast = slow.next;
        slow.next = last;
    }
    // 如果n是奇数，slow指向n/2，把fast指向n/2+2
    else {
        fast = slow.next;
        slow = last;
    }

    while (slow != null && fast != null) {
        if (slow.val != fast.val) {
            return false;
        }
        slow = slow.next;
        fast = fast.next;
    }

    return true;
}

image.png

扩展思路
思路一
同样使用快慢指针，把前一半链表用int存起来，以1->2->3->2->1为例
int half = 0,
走到1的时候，half = 1
走到2的时候, half = 1 + 2 * 10,
走到3的时候，half = 21 + 3 * 10
然后遍历后一半链表，也用int存起来，然后比较
问题：链表数很容易爆int，就算用long、double也很容易爆
思路二
同样使用快慢指针，把前一半、后一半链表分别用String存起来，然后把前一半链表reverse，然后比较
问题：占空间大，且reverse耗时