7.16 Palindrome Linked List

7.16.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 234
• Difficulty: Easy
• Techniques: Two Pointers

7.16.2 Solution - Two Pointers

7.16.2.1 Walkthrough

Find the middle of the linked list using slow and fast pointers. Reverse the second half. Compare the first half with the reversed second half. Restore the list (optional but recommended).

7.16.2.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

7.16.2.3 Code - Java

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode second = reverse(slow);
    ListNode first = head;
    ListNode copy = second;
    boolean result = true;
    while (result && second != null) {
        if (first.val != second.val) result = false;
        first = first.next;
        second = second.next;
    }
    reverse(copy);
    return result;
}