Java: O(n) time, O(1) space


  • 1
    E

    Here are the steps that the algorithm follows:

    1. Initialize two pointers: slow and fast;
    2. Move fast pointer two nodes at a time, move slow pointer one node at a time;
    3. While moving the slow pointer, reverse the list along the way;
    4. Once the midpoint is found, move the pointers towards the ends of the list from the midpoint, comparing nodes' values along the way. Don't forget to restore the reversed half of the list, while moving the pointer towards the head.

    Implementation:

    public class Solution {
        public boolean isPalindrome(ListNode head) {
            boolean result = true;
            // Check whether we have work to do
            if (head == null || head.next == null) return result;
            ListNode slow = head, fast = head, reverseHead = null;
            while (fast != null && fast.next != null) {
                // Move fast pointer two nodes at a time
                fast = fast.next.next;
                // Move slow pointer one node at a time, reversing the first half of the list along the way
                ListNode temp = slow.next;
                slow.next = reverseHead;
                reverseHead = slow;
                slow = temp;
            }
            ListNode mid = slow;
            // Move slow pointer one node forward if the length of the list is odd
            if (fast != null) slow = slow.next;
            // Navigate to the ends of the list, comparing values for equality
            // and restoring the reversed half of the list
            while (slow != null) {
                if (slow.val != reverseHead.val) result = false;
                slow = slow.next;
                ListNode temp = reverseHead.next;
                reverseHead.next = mid;
                mid = reverseHead;
                reverseHead = temp;
            }
            return result;
        }
    }
    

  • 0
    Z

    @Eugeneby Nice solution! Amazing job!


Log in to reply
 

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