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