Recursive! Short, concise JAVA solution. Maintains list without copying.


  • 0
    T
        class Result
        {
            boolean isPalindrome = true;
        }
        
        public boolean isPalindrome(ListNode head) {
            Result res = new Result();
            recurse(head, head, res);
            return res.isPalindrome;
        }
        
        private ListNode recurse(ListNode slow, ListNode fast, Result res)
        {
            if (fast == null)
            {
                // returns the node after the middle to be compared to the slow node in the previous call
                return slow;
            }
            if (fast.next == null)
            {
                // Odd number of nodes, skip the middle one
                return slow.next;
            }
            ListNode slowMirror = recurse(slow.next, fast.next.next, res);
            if (slowMirror.val != slow.val)
            {
                res.isPalindrome = false;
            }
            // returns the next node in the latter half of the list to be compared with 
            // that of the first half (but backwards since we're going back up the recursive stack) 
            return slowMirror.next;
        }
    

    The idea is to keep a slow and fast pointer.
    Once the fast gets to the end, we know the slow is at the middle.
    Return the slow variable as 'slowMirror' which gets compared to the previous call's slow and iterated to the end while going back up the recursive stacks.


Log in to reply
 

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