Palindrome Linked List

Problem

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

Solution

Reverse and Compare: O(n) time, O(1) space

public class Solution {

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;
        fast = head;
        slow = reverse(slow);
        while (slow != null) {
            if (fast.val != slow.val) return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

Analysis

We first use two pointers fast and slow to get the middle node
Then we divide linked list to two parts and reverse the right part, where slow is the head
To make reversed list shorter, we move slow to next if fast != null
And because slow is shorter, we use while (slow != null) after
Before checking, we move the fast to head and slow to its reversed head