2ms Java Solution with comments


  • 1
    X
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head==null || head.next==null) return true;
           
    //find the mid point
            ListNode fast = head;
            ListNode slow = head;
            while(fast.next!=null && fast.next.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            }
            if(fast.next!=null) slow = slow.next; // if it has even elements
            
    //reverse second half list
            ListNode pre = null;
            while(slow!=null){
                ListNode next = slow.next;
                slow.next = pre;
                pre = slow;
                slow = next;
            }
            
    //compare corresponding values
            while(pre!=null){
                if(head.val!=pre.val) return false;
                head = head.next;
                pre = pre.next;
            }
            return true;
        }
    }
    

Log in to reply
 

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