3ms Java solution with explanations, O(n) time and O(1) space


  • 3
    Y
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            //10:25am - 10:42am
            // steps: 
            // 1. find the mid node
            // 2. reverse the list from mid node to tail, not including the mid node
            // 3. compare the first half and the reversed second half, two cases are ok
            //      - pairwise equal
            //      - pairwise equal until the last pair of <midnode, null>
            if (head == null) {
                return true;
            }
            ListNode mid = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                mid = mid.next;
                fast = fast.next.next;
            }
            ListNode rightReversed = reverse(mid.next);
            mid.next = null;
            ListNode left = head;
            ListNode right = rightReversed;
            while (left != null && right != null) {
                if (left.val != right.val) {
                    return false;
                }
                left = left.next;
                right = right.next;
            }
            // right must be null now
            return left == null || left == mid;
        }
        
        private ListNode reverse(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode newHead = reverse(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }
    }

Log in to reply
 

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