Java Solution, 1ms runtime. Beats 88% of the submissions


  • 2
    B
     public boolean isPalindrome(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            ListNode prev = null;
            ListNode temp = null;
            int len = 0;
            //base case
            if(head == null || head.next == null)
                return true;
            // use two pointers to locate the middle of the list and also reverse the first half
            while(fast!=null && fast.next!=null){
                fast = (fast.next).next;
                //reverse the first half of the list
                temp = slow.next;
                slow.next = prev;
                prev = slow;
                slow = temp;
                
            }
            // handle odd number of elements
            if(fast!=null){
                slow = slow.next;
            }
             //iterate over the two lists and check if the elements have same values
            ListNode l1 = prev;
            ListNode l2 = slow;
           
            while(l1!=null && l2!=null && l1.val == l2.val){
                l1 = l1.next;
                l2 = l2.next;
            }
            //if we successfully iterated over all the elements it means the values were same and 
            //hence a palindrome
            return (l1 == null && l2 == null);
        }
    

Log in to reply
 

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