Palindrome Linked List Solution for Capgemini
Company: Capgemini · Difficulty: Easy · Topics: Linked List, Two Pointers
Problem Statement
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
A palindrome is a sequence that reads the same backward as forward.
Examples
Example 1:
Input: head = [1,2,2,1]
Output: true
Explanation: The linked list reads the same forward and backward: 1->2->2->1.
Example 2:
Input: head = [1,2]
Output: false
Explanation: The linked list reads 1->2 forward but 2->1 backward, so it is not a palindrome.
Example 3:
Input: head = [1]
Output: true
Explanation: A single node is always a palindrome.
Example 4:
Input: head = [1,2,3,2,1]
Output: true
Explanation: The linked list reads the same forward and backward: 1->2->3->2->1.
Intuition
To check if a linked list is a palindrome, we need to compare the first half with the reversed second half. Since we can't easily access elements from the end, we need to:
1. Find the middle of the list
2. Reverse the second half
3. Compare the first half with the reversed second half
4. Restore the original list structure (optional)
Approach
Approach 1: Find Middle + Reverse Second Half (Optimal)
1. Find the middle of the linked list using fast and slow pointers
2. Reverse the second half of the list
3. Compare the first half with the reversed second half
4. Optionally restore the original list structure
Approach 2: Convert to Array
1. Convert the linked list to an array
2. Use two pointers to check if the array is a palindrome
3. This approach uses extra space but is simpler
Approach 3: Recursive Approach
1. Use recursion to reach the end of the list
2. Compare the first node with the last node
3. Move inward recursively
4. More complex but elegant
Dry Run
Let's trace through Example 1: head = [1,2,2,1]
Find Middle + Reverse Approach:
- Find middle: slow = 2, fast = null (reached end)
- Middle is at node with value 2
- Reverse second half: 2->1 becomes 1->2
- List becomes: 1->2->1->2 (second half reversed)
- Compare first half (1->2) with reversed second half (1->2)
- They match, so it's a palindrome
Example 2: head = [1,2]
- Find middle: slow = 2, fast = null
- Middle is at node with value 2
- Reverse second half: 2 becomes 2 (single node)
- List becomes: 1->2
- Compare first half (1) with reversed second half (2)
- They don't match, so it's not a palindrome
Key Insights
1. Middle Finding: Use fast and slow pointers to find the middle efficiently
2. Reversing: Reverse the second half to make comparison possible
3. In-place: The optimal solution modifies the list structure temporarily
4. Restoration: Optionally restore the original list structure after checking
Edge Cases
1. Empty list: Return true (empty list is considered palindrome)
2. Single node: Return true
3. Two nodes: Compare the two values
4. Odd length: Middle element doesn't need to be compared
5. Even length: Compare all elements
Time and Space Complexity
- Time Complexity: O(n) - we traverse the list at most 3 times (find middle, reverse, compare)
- Space Complexity: O(1) - we only use a constant amount of extra space