題目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?

思路:使用快慢指針,找到鏈表的中點(diǎn),然后將后半部逆轉(zhuǎn).
最后前后兩部分的元素逐個進(jìn)行對不

public class Solution {
    public boolean isPalindrome(ListNode head) {
        //快慢指針, lower到中點(diǎn), 然后后半部分逆轉(zhuǎn).  然后分別比較這兩部分的值即可
        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;
    }
}