234. Palindrome Linked List - Detailed Explanation
Problem Statement
Description:
Given the head of a singly linked list, determine if the linked list is a palindrome. 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 1 → 2 → 2 → 1 from both directions.
-
Example 2:
- Input: head = [1, 2]
- Output: false
- Explanation:
The linked list reads 1 → 2 in the forward direction and 2 → 1 in reverse, so it is not a palindrome.
Constraints:
- The number of nodes in the list is in the range [1, 10⁵].
- -10⁵ ≤ Node.val ≤ 10⁵
Hints
-
Two-Pointer Technique:
Use a fast and slow pointer to find the midpoint of the linked list. The fast pointer moves twice as fast as the slow pointer. -
Reversing a List:
After finding the midpoint, reverse the second half of the linked list. Then, compare it with the first half. -
Comparison:
Compare node by node for the two halves. If all corresponding nodes are equal, the list is a palindrome.
Approaches
Approach 1: Reverse the Second Half
Idea:
- Use the fast and slow pointer technique to locate the midpoint.
- Reverse the second half of the list.
- Compare the first half and the reversed second half node by node.
- Optionally, restore the list to its original order if needed.
Pros:
- Time complexity is O(n) and space complexity is O(1).
Cons:
- Modifies the list (although it can be restored).
Approach 2: Use a Stack
Idea:
- Traverse the first half of the list and push its nodes’ values onto a stack.
- For the second half, pop from the stack and compare with the current node’s value.
- If all comparisons match, the list is a palindrome.
Pros:
- Straightforward to implement.
Cons:
- Requires O(n) extra space for the stack.
Approach 3: Convert to Array
Idea:
- Convert the linked list into an array.
- Use two pointers to check if the array is a palindrome.
Pros:
- Easy to implement.
Cons:
- Uses O(n) extra space; less optimal than reversing the list.
Code Implementations
Python Implementation
Java Implementation
Complexity Analysis
-
Time Complexity:
- Finding the midpoint takes O(n).
- Reversing the second half takes O(n).
- Comparing the two halves takes O(n).
- Overall, the time complexity is O(n).
-
Space Complexity:
- The solution uses O(1) extra space (in-place reversal), aside from the recursion stack in case of a recursive solution (which is not used here).
Step-by-Step Walkthrough with Visual Example
Consider the linked list: [1, 2, 2, 1]
-
Finding the Midpoint:
- Initialize both
slowandfastat the head. - After one iteration:
slowmoves to 2 (second node)fastmoves to 2 (third node)
- After next iteration:
slowmoves to 2 (third node)fastmoves beyond the last node.
- The midpoint is at the third node (value 2).
- Initialize both
-
Reversing the Second Half:
- Original second half: 2 → 1
- After reversal: 1 → 2
-
Comparing the Two Halves:
- First half: 1 → 2
- Reversed second half: 1 → 2
- Each corresponding pair is equal, so the list is a palindrome.
Common Mistakes
-
Incorrect Midpoint Calculation:
Be careful with the fast and slow pointer technique; in an even-length list, choose the correct starting point for the second half. -
Reversing the List Incorrectly:
Ensure that the pointers are updated correctly when reversing the second half. -
Ignoring Edge Cases:
Always consider single-node lists and empty lists.
Edge Cases
-
Single Node:
A list with only one node is always a palindrome. -
Empty List:
Although not common in problem constraints, an empty list can be considered a palindrome. -
Even vs. Odd Length:
For odd-length lists, the middle element does not need to be compared.
Alternative Variations and Related Problems
-
Alternative Variation:
Instead of modifying the list (by reversing the second half), one can copy the values into an array and use two pointers to check for a palindrome. -
Related Problems for Further Practice:
- Reverse Linked List
- Merge Two Sorted Lists
- Reorder List
GET YOUR FREE
Coding Questions Catalog
