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

解题思路：链表划分（链表部分反转 + 双指针）

● 方式一：遍历一次，转换为字符串或者数组，然后【相向】双指针判断回文
代码略。

● 方式二：链表分成两部分，后半部分进行链表反转，然后【同向】双指针判断回文
(1) 遍历一次，确定链表的长度len。
(2) 分成两部分。前半部分节点数：len/2，后半部分节点数：len/2 或者 len/2 + 1（即后半部分可能会更长）。
(3) 将后半部分链表反转
(4) 同向双指针判断对应位置是否相等

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode secondHead = null;
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true; // 0个或1个时
        // 1. 第一遍遍历确定长度
        ListNode tmp = head;
        int len = 0;
        while(tmp != null){
            len++;
            tmp = tmp.next;
        }
        // 2. 后半部分翻转，找到前半部分的尾巴
        int i = 0;
        tmp = null;
        while(i < (len/2)){
            if(tmp == null) tmp = head;
            else tmp = tmp.next;
            i++;
        }
        // 3. 拆成两个链表，后半部分反转
        ListNode head2 = tmp.next;
        tmp.next = null;
        recur(head2);
        // 4. 判断前半部分，后半部分是否能匹配上（后半部分可能会长一点）
        ListNode first = head;
        ListNode second = secondHead;
        while(first != null && second != null){
            if(first.val != second.val) return false;
            first = first.next;
            second = second.next;
        }
        return true;
    }
    // 反转链表
    public ListNode recur(ListNode node){
        if(node != null && node.next == null){
            secondHead = node;
            return node;
        }
        ListNode nextNode = recur(node.next);
        nextNode.next = node;
        node.next = null; // 防止成环
        return node;
    }
}

类似的题目：143. 重排链表 - 力扣（LeetCode）
● 相似点：
(1) 将链表分成两部分
 本题处理的时候是后半部分要么和前半部分长度相等，要么更大；（更方便处理）
 143. 处理的时候是后半部分要么和前半部分长度相等，要么更少；（更方便处理）
(2) 后半部分链表反转
 本题用双指针比较即可
 143. 用双指针来重构链表