Algorithm-Day24-Palindrome-Linked-List-lc-234

🧩 Problem Description

Given the head of a singly linked list, return true if it is a palindrome, or false otherwise.

Example:

Input: 1 → 2 → 2 → 1
Output: true

Input: 1 → 2
Output: false

💡 Brute Force Idea

• Store values in a list or array.
• Check if the list is a palindrome.

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    while (head != null) {
        vals.add(head.val);
        head = head.next;
    }
    int i = 0, j = vals.size() - 1;
    while (i < j) {
        if (!vals.get(i).equals(vals.get(j))) return false;
        i++;
        j--;
    }
    return true;
}

• Time: O(n)
• Space: O(n)
• ✅ Easy to implement, but not in-place.

---

💡 Optimal Approach (In-Place, O(1) Space)

✨ Strategy

1. Find the middle of the list (fast and slow pointers).
2. Reverse the second half.
3. Compare the two halves.
4. (Optional) Restore the list.

---

🔢 Java Code

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // Step 1: Find middle
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse second half
        ListNode secondHalf = reverse(slow);

        // Step 3: Compare
        ListNode p1 = head, p2 = secondHalf;
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

---

⏱ Time and Space Complexity

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

---

✍️ Summary

• Key techniques used:
  • Fast/slow pointer
  • In-place list reversal
  • Two-pointer comparison
• This approach keeps space minimal while maintaining correctness.

This is a great example of combining several core linked list techniques in a single elegant solution.