Palindrome List

Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively.

Notes:

For example,

List 1-->2-->1 is a palindrome.
List 1-->2-->3 is not a palindrome.

Method:

Reverse the second half of the linked list, and then scan the linkedlist from the start and end at the same time.

For example, 1-> 2 -> 1 becomes 1 -> 2 and 2 <- 1
1 -> 2 -> 2 -> 1 becomes 1-> 2 and 2 <- 1

Solution:

Time: o(n)
Space: O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    // null <- 1 <- 2 -> 3 -> 4
    private ListNode reverse(ListNode A) {
        if (A == null || A.next == null) return A;
        ListNode curr = A;
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    
    private ListNode mid(ListNode A) {
        ListNode slow = A;
        ListNode fast = A.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // if list is even, return the next slow as mid
        // for example, 1 -> 2 -> 3 -> 4, we want 3
        if (fast != null) {
            slow = slow.next;
        }
        return slow;
    }
    
    public int lPalin(ListNode A) {
        ListNode mid = mid(A);
        ListNode tail = reverse(mid);
        while (A != null && tail != null) {
            if (A.val != tail.val) {
                return 0;
            }
            A = A.next;
            tail = tail.next;
        }
        return 1;
    }
}