234. Palindrome Linked List

题目234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?

思路:使用快慢指针,找到链表的中点,然后将后半部逆转.
最后前后两部分的元素逐个进行对不

public class Solution {
    public boolean isPalindrome(ListNode head) {
        //快慢指针, lower到中点, 然后后半部分逆转.  然后分别比较这两部分的值即可
        if(head == null || head.next == null){
            return true;
        }
        
        if(head.next.next == null){
            return head.val == head.next.val;
        }
        
        ListNode lowerNode = head;
        ListNode fastNode = head;
        while(fastNode.next != null && fastNode.next.next != null){
            lowerNode = lowerNode.next;
            fastNode = fastNode.next.next;
        }
        
        ListNode secondNode = lowerNode.next;
        lowerNode.next = null;
        ListNode secondHead = new ListNode(1);
        ListNode tempNode = null;
        while(secondNode != null){
            tempNode = secondNode.next;
            secondNode.next = secondHead.next;
            secondHead.next = secondNode;
            secondNode = tempNode;
        }
        
        secondNode = secondHead.next;
        ListNode firstNode = head;
        while(secondNode != null){
            if(secondNode.val != firstNode.val){
                return false;
            }
            firstNode = firstNode.next;
            secondNode = secondNode.next;
        }
        
        return true;
    }
}