【LC234】回文链表

这道题可以分解为寻找链表中间节点+翻转链表：

先找到链表的中间节点，从中间节点开始翻转后半段链表，再从head和tail同时遍历看两段链表是否一致

以下是代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode n1 = head;
        ListNode n2 = head;
        while(n1 != null && n1.next != null){
            n1 = n1.next.next;
            n2 = n2.next;
        }
        ListNode tail = reverse(n2);
        while(head != null && tail != null){
            if(head.val != tail.val){
                return false;
            }
            head = head.next;
            tail = tail.next;
        }
        return true;

    }

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