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


  • 1
    A

    Slow and Fast pointers start with pointing to head. Move slow by 1 node, Fast by 2 nodes. When Fast reaches the end of the list, slow is at the middle node. Now call another function with slow as the head to reverse the latter half of the list. Then compare the 1st and the 2nd half.

    public boolean isPalindrome(ListNode head) {
            if(head==null||head.next==null) return true;
            ListNode fast, slow;
            fast = slow = head;
            
            while(fast!=null&&fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            //fast will be null if number of nodes is even
            if(fast!=null) slow=slow.next;
            
            slow = reverseList(slow);
            fast = head;
            
            while(fast!=slow && slow!=null){
                if(fast.val!=slow.val)
                    return false;
                fast=fast.next;
                slow=slow.next;
            }
            return true;
        }
        
        public ListNode reverseList(ListNode head) {
            if(head.next==null) return head;
            ListNode prev, curr, next;
            prev = next = null;
            curr = head;
            
            while(curr!=null){
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    

Log in to reply
 

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