2.6 Palindrome: Implement a function to check if a linked list is a palindrome.

To approach this problem, we can picture a palindrome like e -> 1 - > 2 -> 1 -> e. We know that, since it's a palindrome, the list must be the same backwards and forwards. This leads us to our first solution.

Solution #1: Reverse and Compare
Our first solution is to reverse the linked list and compare the reversed list to the original list. If they're the same, the lists are identical.
Note that when we compare the linked list to the reversed list, we only actually need to compare the first half of the list. If the first half of the normal list matches the first half of the reversed list, then the second half of the normal list must match the second half of the reversed list.

/**
 * 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) {
        ListNode reversed = reverseAndClone(head);
        return isEqual(head, reversed);
    }
    ListNode reverseAndClone(ListNode node){
        ListNode head =null;
        while(node!=null){
            ListNode n = new ListNode(node.val);
            n.next = head;
            head=n;
            node =node.next;
        }
        return head;
    }
    boolean isEqual(ListNode one, ListNode two){
        while(one!=null&&two!=null){
            if(one.val!=two.val) return false;
            one=one.next;
            two=two.next;
        }
        return one ==null && two==null;
    }
}

Observe that we've modularized this code into reverse and isEqual functions. We've also created a new class so that we can return both the head and the tail of this method. We could have also returned a twoelement array, but that approach is less maintainable.

This can be solved by reversing the 2nd half and compare the two halves.

public boolean isPalindrome(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    if (fast != null) { // odd nodes: let right half smaller
        slow = slow.next;
    }
    slow = reverse(slow);
    fast = head;
    
    while (slow != null) {
        if (fast.val != slow.val) {
            return false;
        }
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}

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