Java 1ms solution (linear time, constant space) w/ explanation


  • 1
    C
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            // traverse the list once to count the number of elements and determine the midpoint
            ListNode current = head;
            int nodeCount = 0;
            while (current != null) {
                nodeCount++;
                current = current.next;
            }
            int midCount = nodeCount/2;
            // reverse the first half of the list
            current = head;
            ListNode previous = null;
            ListNode temp = null;
            for (int ii = 0; ii < midCount; ii++) {
                temp = current.next;
                current.next = previous;
                previous = current;
                current = temp;
            }
            // if there are an odd number of elements, skip the middle element
            if (nodeCount % 2 == 1) {
                current = current.next;
            }
            // compare the second half of the list to the reversed first half
            // "previous" points to the head of the reversed first half
            for (int jj = 0; jj < midCount; jj++) {
                if (current.val != previous.val) {
                    return false;
                } else {
                    current = current.next;
                    previous = previous.next;
                }
            }
            return true;
        }
    }

  • 0
    S

    very nice solution! and I agree: I wouldn't classify this as easy!

    I think you should also restore the fist half of the list to its original place before returning.


Log in to reply
 

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