leetcode 234. 回文链表（快慢指针+链表倒置）

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

示例 1:

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

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

代码

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

    if(head==null||head.next==null) return true;
    ListNode fast=head,slow=head,pre=null;
    while (fast!=null&&fast.next!=null)
    {
          
   
        pre=slow;
        slow=slow.next;
        fast=fast.next.next;
    }//快慢指针找出中点


    pre.next=null;
    //从中点切断链表
    pre=null;

    while (slow!=null)//倒置后部分链表
    {
          
   
        ListNode temp=slow.next;
        slow.next=pre;
        pre=slow;
        slow=temp;
    }

     while (pre!=null&&head!=null)//将两个链表比较
     {
          
   
         if(pre.val!=head.val) return false;
         pre=pre.next;
         head=head.next;
         
     }
     return true;
    }
}