Linked list palindrome judgment

link ： Palindrome structure of linked list

Ideas ： If it's a competition , Turn the linked list directly into an array to do , Convenient and quick . As an interview question , With the restrictions of the interviewer, it's not enough . Because this is a one-way linked list , There is no way to traverse to the last point and then traverse from the back to the front , So we must traverse to the intermediate node first , Then flip the linked list from the intermediate node to the last node

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // Find the intermediate node 
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        // Flip the second half of the linked list 
        ListNode pre = slow;
        slow = slow.next;
        pre.next = null;
        while(slow != null){
            ListNode tmp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = tmp;
        }
        
        // Comparison is equal 
        while(head != null && pre != null){
            if(head.val != pre.val)return false;
            head = head.next;
            pre = pre.next;
        }
        
        return true;
    }
}