Java solution with detailed comments (Run time 2ms)


  • 0
    L

    Re: Java-Easy-Reverse 2nd half of list and compare to first half

    /**
     * Refers to @arjun033 solution and rewrote
     * 1. Get the middle point of the list
     * 2. Reverse the 2nd half of the list
     * 3. Compare 1st half and reversed 2nd half
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            //Empty list [] returns true based on test case
            //"head.next == null": avoid the following 3 steps checking.
            return true;
        }
    
        //1. Get the middle point of the list
        ListNode middleNode = getMiddle(head);
    
        //2. Reverse the 2nd half of the list
        ListNode reversed2ndHalf = reverse(middleNode);
    
        //3. Compare 1st half and reversed 2nd half
        return compare(head, reversed2ndHalf);
    }
    
    private ListNode getMiddle(ListNode head) {
        ListNode fast, slow;
        fast = head;
        slow = head;
    
        //When fast race to end, slow will be at the middle point
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;  //2x fast
            slow = slow.next;       //1x fast
        }
    
        //If the total number of list is even, move slow one more step
        if (fast.next != null) {
            slow = slow.next;
        }
    
        return slow;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev/*Reversed head node*/, curr, next /*Used for move forward*/;
        prev = null;
        curr = head;
    
        while (curr != null) {
            next = curr.next;   //Prepare move forward
            curr.next = prev;   //Link backward
            prev = curr;        //Move "backward link node prev" foward
            curr = next;        //Move forward
        }
    
        return prev;
    }
    
    private boolean compare(ListNode source, ListNode target) {
        while ( target != null) {
            if( source.val != target.val) {
                return false;
            } else {
                source = source.next;
                target = target.next;
            }
        }
        return true;
    }
    

Log in to reply
 

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