Problem

Implement a function to check if a linked list is a palindrome.

Example

Given 1->2->1, return true.

Solution

public class Solution {
    public boolean isPalindrome(ListNode head) {
        // O(n) time and O(n) space
        if (head == null) return true;
        ListNode p = head;
        ListNode tail = reverse(p);
        ListNode p1 = head, p2 = tail;
        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
        
    }
    public ListNode reverse(ListNode head) {
        ListNode tail = null; //tail is the tail
        while (head.next != null) {
            ListNode temp = new ListNode(head.next.val);
            temp.next = tail;
            tail = temp;
            head = head.next;
            //example: head = 1-2-3-4-null, tail = null
            //temp = 2, tail = 2-null, head = 2
            //temp = 3, 3-2, tail = 3, 3-2, head = 3
            //... tail = 4-3-2
            //so, given 1-2-3-2-1 reverse: 1-2-3-2 compare: true
        }
        return tail;
    }
}