Palindrome Linked List

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

/**
 * 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) return true;
        if (head.next == null) return true;

        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // reverse the second half
        ListNode secondHalfHeader = slow.next;
        slow.next = null;

        ListNode reverseHead = reverseNode(secondHalfHeader);

        ListNode runner1 = head;
        ListNode runner2 = reverseHead;

        while (runner1 != null && runner2 != null) {
            if (runner1.val != runner2.val) {
                return false;
            }

            runner1 = runner1.next;
            runner2 = runner2.next;
        }

        if (runner1 == null  && runner2 == null) {
            return true;
        } else if (runner1 != null && runner1.next == null) {
            return true;
        } else if (runner2 != null && runner2.next == null) {
            return true;
        }

        return false;
    }

    public ListNode reverseNode(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;

        ListNode nextNode = head.next;
        ListNode result = reverseNode(head.next);
        nextNode.next = head;
        head.next = null;
        return result;
    }
}