[数据结构与算法]剑指 Offer II 027. 回文链表

剑指 Offer II 027. 回文链表：

题目链接 ：剑指 Offer II 027. 回文链表

题目：给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

思路：

1、找到链表中间结点。
2、两部分链表前后分开，后半部分逆转。
3、两部分按位比较。

AC代码：

/**
 * 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 findMid(ListNode head)
    {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode fast=dummy;
        ListNode slow=dummy;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    private ListNode reverse(ListNode head)
    {
        ListNode cur=head;
        ListNode pre=null;
        while(cur!=null)
        {
            ListNode tmp=null;
            tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }

    public boolean isPalindrome(ListNode head) {
     
     ListNode cur=head;
     ListNode mid=findMid(cur);
     ListNode re=reverse(mid.next);
     mid.next=null;
     while(cur!=null&&re!=null)
     {
         if(cur.val!=re.val)
         {
             return false;
        
         }
            cur=cur.next;
            re=re.next;
         
     }
    return true;
    }
       
}