思路

  • 1.利用快慢指针找到中间结点
  • 2.翻转后面部分的链表
  • 3.判断是否为回文结构

图解

alt

解题过程

  • 1.先判断头结点是否为空,判断是否只有一个结点
  • 2.通过快慢指针找到中间结点slow
  • 3.对slow后面的链表进行翻转
  • 4.head和slow一个从前往后,一个从后往前进行比较
  • 5.在偶数情况下,当head的下一个结点为slow时,不需要相遇,也为回文结构
  • 6.当循环走完,证明符合回文条件,返回true

代码

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return false;
        }
        if(A.next==null){
            return true;
        }
       ListNode fast = A;
       ListNode slow = A;
         //寻找中间结点
       while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
       }
        //翻转
       ListNode cur = slow.next;//cur代表当前需要翻转的结点
       while(cur!=null){
        ListNode curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur=curNext;
       }
       //一个从前往后,一个从后往前,进行比较, 直到slow和head相遇
       while(slow != A){
        if(slow.val != A.val){
            return false;
        }
        if(A.next==slow){//走到这里两个val值一样,偶数情况
            return true;
        }
        A= A.next;
        slow = slow.next;
       }
       return true;
    }  
}