题目链接

英文链接：https://leetcode.com/problems/palindrome-linked-list/

中文链接：https://leetcode-cn.com/problems/palindrome-linked-list/

题目详述

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

示例 1:

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

示例 2:

1 2	输入: 1->2->2->1 输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？？

题目详解

解决这种问题免不了对结点的 next 进行操作，最好的方式是先用纸笔画图模拟一下操作过程，再来写代码。由于链表不支持随机存取，故需要对链表进行反转操作，可以反转前半部分链表，也可以反转后半部分链表（当然，也可以反转整个链表，不过没必要）。本题可以用快慢指针进行处理，fast 指针每次走两步，slow 每次指针走一步。要注意链表结点总数奇偶性的差异：为偶数时，fast 指针不能再前进时，fast 指向 null，slow 指向下中位数的结点；为奇数时，fast 指针不能再前进时，fast 指向尾结点，slow 指向中心结点。

下面是反转前半部分链表版本：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class LeetCode_00234 {

    // 反转前半部分链表
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 反转前半部分链表
        ListNode cur = head;
        ListNode pre = null;
        while (cur != slow) {
            ListNode nxet = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxet;
        }
        // 如果长度为奇数，跳过中心结点
        if (fast != null) {
            slow = slow.next;
        }
        while (pre != null && slow != null) {
            if (pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}

下面是反转后半部分链表版本：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class LeetCode_00234 {

    // 反转后半部分链表n
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 如果长度为奇数，跳过中心结点
        if (fast != null) {
            slow = slow.next;
        }
        // 反转后半部分链表
        ListNode newHead = reverseList(slow);
        while (newHead != null) {
            if (head.val != newHead.val) {
                return false;
            }
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}