Palindrome Linked List

Question (LC.234)

Given a singly linked list, determine if it is a palindrome.

Example

I: 1 -> 2 -> 1
O: true

Analysis

Need to use L/R pointers to compare the first half and the second half.

Approach

Step 1 Find the mid point
Step 2 reverse the second half
Step 3 compare two lists
Step 4 (optional) reverse the second half back

Code

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    ListNode mid = findMid(head);
    ListNode l2 = reverseList(mid);
    ListNode l1 = head;
    // compare
    while (l2 != mid) {
        if (l1.val == l2.val) {
            l1 = l1.next;
            l2 = l2.next;
        } else {
            break;
        }
    }
    return l2.val == l1.val;
}

private ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

private ListNode reverseList(ListNode head) {
    ListNode prev = head;
    ListNode current = head.next;
    ListNode temp;
    while (current != null) {
        temp = current.next;
        current.next = prev;
        prev = current;
        current = temp;
    }
    return prev;
}