Simple java 0ms beat 100% solution


  • 0
    P
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) //none or one
                return true;
            ListNode slow = head;
            ListNode fast = head;
            ListNode old = head;
            //find the middle node
            while (fast != null && fast.next != null) {
                old = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            //divide it to two equal sub lists
            if (fast != null) { //slow is the middle of odd notes list
                fast = slow;
                slow = null;
            } else { //even nodes list
                fast = slow;
                old.next = null;
            }
            //reverse the last half list
            old = null;
            while (fast != null) {
                ListNode t = fast.next;
                fast.next = old;
                old = fast;
                fast = t;
            }
            //check palindrome of two sub lists
            slow = head;
            fast = old;
            while (slow != null && fast != null) {
                if (slow.val != fast.val)  return false;
                slow = slow.next;
                fast = fast.next;
            }
            return slow == fast;
        }
    

  • 0
    B
    This post is deleted!

  • 0
    B

    if the case is:
    1 -> 1 -> 1 -> 2 -> 1 -> 1 -> 1
    your code would return false and fail because this is still palindrome.
    But I don't know why your code pass the test.


  • 0
    P

    Thank you for your comments. When I had run the program, it was passed with no problem. I guess at that time, the list has no repeated elements in one side of palindrome. So after consider your case: 1->1->2->1->1 or 1->1->1->1, and etc. I have modified the code and the time is still O(n) and space is O(1).

        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) //none or one
                return true;
            ListNode slow = head;
            ListNode fast = head;
            ListNode old = head;
            //find the middle
            while (fast != null && fast.next != null) {
                old = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            //divide to two sub list
            if (fast != null) { //odd
                fast = slow;
                slow = null;
            } else {
                fast = slow;
                old.next = null;
            }
            //revert the last half list
            old = null;
            while (fast != null) {
                ListNode t = fast.next;
                fast.next = old;
                old = fast;
                fast = t;
            }
            //check palindrome of two lists
            slow = head;
            fast = old;
            while (slow != null && fast != null) {
                if (slow.val != fast.val)  return false;
                slow = slow.next;
                fast = fast.next;
            }
            return slow == fast;
        }
    

Log in to reply
 

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