Fast Java Solution


  • 0
    R

    Use two pointers (prev and fast) to find the end and middle of the list.
    Fast is incremented at twice the speed as prev.
    We will reverse the first half of the list as we increment prev. When fast reaches the end, prev will be start of the reversed list. Curr will be the start of the unreversed list.
    Traverse both and compare.

    public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) return true;
            if (head.next.next == null) return (head.val == head.next.val) ? true: false;
            
            ListNode prev = head, curr = head.next, next = head.next.next, fast = head;
            
            while (true) {
                fast = fast.next.next;
                if (fast == null || fast.next == null) {
                    break;
                }
                
                if (prev == head) prev.next = null; // ground the reversed list
                // reversing
                curr.next = prev;
                prev = curr;
                curr = next;
                next = next.next;
                
            }
            
            if (fast != null)
                curr = curr.next;
            
            while (prev != null && curr != null) {
                if (prev.val != curr.val) return false;
                prev = prev.next;
                curr = curr.next;
            }
            
            return true;
        }
    

Log in to reply
 

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