Check if Singly Linked List is Palindrome

Problem Statement

Given the head of a singly linked list, determine if it is a palindrome. A palindrome reads the same forwards and backwards.

Example

Input: 1 -> 2 -> 2 -> 1 -> null Output: true Input: 1 -> 2 -> 3 -> 2 -> 1 -> null Output: true Input: 1 -> 2 -> 3 -> null Output: false Input: 1 -> null Output: true

---

Brute Force Approach 1 (Using Array/Stack)

Intuition

Store all values in an array, then check if the array is a palindrome using two pointers.

Algorithm

1. Traverse the list and store all values in an array
2. Use two pointers (start and end) to check palindrome
3. If all pairs match, it's a palindrome

Implementation

Complexity Analysis

• Time Complexity: O(n) - Traverse list + check array
• Space Complexity: O(n) - Store all values

---

Brute Force Approach 2 (Using Stack)

Intuition

Push all values to a stack, then compare while popping. The stack reverses the order naturally.

Implementation

---

Optimal Approach (Reverse Second Half)

Intuition

1. Find the middle of the list
2. Reverse the second half
3. Compare both halves
4. (Optional) Restore the list

This uses O(1) extra space.

Algorithm

1. Find middle using slow-fast pointers
2. Reverse the second half
3. Compare first half with reversed second half
4. If all match, it's a palindrome
5. (Optional) Reverse second half back to restore

Visualization

Original: 1 -> 2 -> 3 -> 2 -> 1 Step 1: Find middle (slow pointer) 1 -> 2 -> 3 -> 2 -> 1 ↑ mid Step 2: Reverse second half First half: 1 -> 2 -> 3 Second half: 1 -> 2 (reversed from 2 -> 1) Step 3: Compare 1 == 1 ✓ 2 == 2 ✓ (middle 3 can be skipped for odd length) Result: Palindrome!

Implementation

Complexity Analysis

• Time Complexity: O(n) - Find middle + reverse + compare
• Space Complexity: O(1) - Only using pointers

---

Alternative: Recursive Approach

Intuition

Use recursion to reach the end, then compare with a front pointer while backtracking.

Implementation

Complexity Analysis

• Time Complexity: O(n) - Visit each node once
• Space Complexity: O(n) - Recursive call stack

---

Comparison of Approaches

| Approach | Time | Space | Modifies List | |----------|------|-------|---------------| | Array | O(n) | O(n) | No | | Stack | O(n) | O(n) | No | | Reverse Half | O(n) | O(1) | Yes (can restore) | | Recursion | O(n) | O(n) | No |

---

Key Takeaways

1. The optimal O(1) space solution combines multiple techniques:
   • Finding middle (slow-fast pointers)
   • Reversing a linked list
   • Two-pointer comparison
2. Always consider restoring the list after modification (good practice)
3. The recursive approach is elegant but uses O(n) stack space
4. For odd length lists, the middle element doesn't need comparison
5. This is a classic interview problem (LeetCode #234)
6. Understanding this solution shows mastery of linked list fundamentals