给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

我常觉得解链表题好比理耳机线，通常链表题都不会涉及太多的算法，要得是细心和耐心，一不小心就可能缠作一团，所以做链表题大家拿笔画一画，就比较清楚了。

“回文”大家应该都知道啥意思，就是镜像，第一个和最后一个一样，第二个和倒数第二个一样……，以此类推。但是，链表没法像数组那样直接按索引随机读取，所以得把后半段反转一下，之后一个指针指向头，一个指针指向中间，依次往后检查。这一个题相融合了三个题：链表反转、寻找链表中点、判断回文。

先写链表反转，没啥好说的。方法也有好多种，记住一种就行了，记的多了还容易乱，我比较习惯头插法，啥叫头插法，就是不断的将“头”的后一个节点移到头的前一个节点，直到最后一个节点，就完成了反转，如下。

private ListNode reverse(ListNode head) {
    ListNode dummy = new ListNode(-1, head);
    ListNode cur = head;
    while (cur.next != null) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = dummy.next;
        dummy.next = next;
    }
    return dummy.next;
}

然后找中点，采用快慢指针的方式，快的一次走两步，慢的一次走一步，当快的走到末尾时，慢的正好是链表的一半。思想很简单，就是细节得想明白。比如，快的一次走两步，那是一步一步走走两次还是一次走两步，走到“末尾”是走到最后一个节点，还是走到不足两步就停下来，那如果这时候停下来，慢的还正好在中点这个位置上吗？

先来看是一步一步走，还是一次走两步。

一次走一步，走两次，如下。

private ListNode getMiddle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
	while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
        if (fast.next != null) {
            fast = fast.next;
        }
    }
    return slow;
}

一次走两步。

private ListNode getMiddle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

是不是看起来差不多？实际上是不一样的，当n为偶数时，前一种会多走一步，n为奇数时两者一样。其实本题用哪个都行，关键你要关注到两者的不同，后面的代码也因之不同。

再来看第二个问题，走到“末尾”是走到最后一个节点，还是走到不足两步就停下来，如果这时候停下来，慢的还正好在中点这个位置上吗？假设链表上有n个节点，也就是能走n-1步，这意味着奇数个节点有偶数步，偶数个节点有奇数步。比如，如果链表有3个节点，那只有2步，有4个节点，有3步，对于快指针来说偶数步正好走到最后一个节点，奇数步走到倒数第二个节点；对于慢指针来说，偶数步走到第(n-1)/2 + 1个节点，如果n为3，那应该是走到第2个节点，正好是中间，奇数步的话，如果是“一次走两步”是走到第(n-1-1)/2 + 1个节点，如果n为4，也是走到第2个节点，链表前半段的末尾。还记得上面说，如果“一步一步走”，会多走一步，也就是会落在第3个节点，即后半段的开头。因此，第二个问题的答案可以笼统的说，慢指针会落在链表的中间节点上，只不过有时候不同走法前后会相差一个。

现在问题就简单了，下面是我写的第一个版本，当时的想法是找到中点，中点的下一个是后半段的头，然后从中间断开，将后半段反转，然后依次判断前半段和后半段反转后的节点值，只有完全一样才会继续往后走，否则直接返回false，不知道大家看出问题没。

public boolean isPalindrome(ListNode head) {
    // 采用一次走两步的方式
    ListNode pre = getMiddle(head);
    ListNode mid = pre.next;
    pre.next = null;

    if (mid == null) return true;
    ListNode head2 = reverse(mid);
    while (head != null || head2 != null) {
        if (head != null && head2 != null) {
            if (head.val != head2.val) return false;
            head = head.next;
            head2 = head2.next;
        } else {
            return false;
        }
    }
    return true;
}

上面的写法，忽略了遇到奇数个节点时，getMiddle切割的前后两段节点数是不一样的，前半段会多一个，这会导致head != null而head2 == null情况出现，进而返回false，比如[1, 2, 1]，下面是改正后的。

public boolean isPalindrome(ListNode head) {
    // 采用一次走两步的方式
    ListNode pre = getMiddle(head);
    ListNode mid = pre.next;
    pre.next = null;
    if (mid == null) return true;
    ListNode head2 = reverse(mid);
    while (head != null && head2 != null) {
        if (head.val != head2.val) return false;
        head = head.next;
        head2 = head2.next;
    }
    return true;
}

事实上，head != null && head2 != null的判断条件可以进一步精简为head2 != null，因为getMiddle已经对前后两端的长度做了保证，前半段的长度是不会小于后半段的。前后两段也可以不断开，getMiddle使用的是“一次走两步”的方式，如果用的是“一次走一步走两次”的方式，返回值直接就是head2，不用再下一个了。