题解 | #链表的回文结构#

思路

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

图解

解题过程

• 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;
    }  
}