Leetcode: 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?

Understand the problem:
Since the problem asks for O(n) time and O(1) space, we cannot create additional data structure to store the values. The steps to solve the problem are:
  -- 1. Find the middle of the list. 
  -- 2. Reverse the right half of the list. 
  -- 3. Compare the left half and right half.

Code (Java):

/**
 * 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;
        }
        
        int len = getLength(head);
        
        ListNode mid = findMiddle(head);
        
        ListNode newHead;
        
        if (len % 2 == 0) {
            newHead = mid.next;
            mid.next = null;
        } else {
            ListNode dummyNode = new ListNode(mid.val);
            dummyNode.next = mid.next;
            newHead = dummyNode;
        }
        
        // Step 2: reverse the list
        newHead = reverseList(newHead);
        
        // Step 3: compare the list
        ListNode p = head;
        ListNode q = newHead;
        while (p != null && q != null) {
            if (p.val != q.val) {
                return false;
            }
            
            p = p.next;
            q = q.next;
        }
        
        return true;
    }
    
    private int getLength(ListNode head) {
        ListNode p = head;
        int len = 0;
        
        while (p != null) {
            len++;
            p = p.next;
        }
        
        return len;
    }
    
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}