[leetcode] problem 234 – palindrome linked list

public class  {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null)
        return true;
    
    ListNode middle = findMiddle(head);
    middle.next = reverse(middle.next);

    ListNode node1 = head;
    ListNode node2 = middle.next;

    while (node1 != null && node2 != null) {
        if (node1.val != node2.val)
            return false;
        
        node1 = node1.next;
        node2 = node2.next;
    }

    return true;
}

private ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = slow.next;

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

    return slow;
}

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

    return prev;
}