Easy Java Solution with Comments


  • 0
    O
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) return true;
            ListNode oneStep = head;
            ListNode pre = null;
            ListNode twoStep = head;
            while(twoStep != null && twoStep.next != null) {
                pre = oneStep; // Used to when there are even number of nodes.
                oneStep = oneStep.next;
                twoStep = twoStep.next.next;
            }
            // If twoStep is null, it means there are even number of nodes. We need to break down the original list
            // and then do the reverse
            // Even number of nodes, final state as follows.
    
            //         oneStep     twoStep
            //            |          |
            // 1 -> 2 -> 2 -> 1 -> null
    
            // If twoStep.next is null, the list is already broken by reverse() method. No need to break up the list.
            // Odd number of nodes, final state as follows.
    
            //   oneStep  twoStep
            //      |     |
            // 1 -> 2 -> 1 -> null
            if(twoStep == null) pre.next = null;
    
            // A linked list is palindrome iff the reverse of half of it starting at half point equals another half.
            return equals(reverse(oneStep), head);
        }
        
        protected boolean equals(ListNode head1, ListNode head2) {
            while(head1 != null && head2 != null) {
                if(head1.val != head2.val) return false;
                head1 = head1.next;
                head2 = head2.next;
            }
            return head1 == null && head2 == null;
        }
        
        protected ListNode reverse(ListNode head) {
            ListNode node = head;
            ListNode newHead = null;
            while(node != null) {
                ListNode next = node.next;
                node.next = newHead;
                newHead = node;
                node = next;
            }
            return newHead;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.