Palindrome Linked List
Problem Description
Question
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input:head=[1,2,2,1]
1
2
2
1
null
Output:true
true
Example 2:
Input:head=[1,2]
1
2
null
Output:false
false
Constraints:
- The number of nodes in the list is in the range [1, 105].
- 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
Solve it on LeetCode
Approaches
1. Convert to Array and use Two-Pointer Technique
Intuition:
The easiest way to determine if a linked list is a palindrome is to convert the linked list into an array and then use the two-pointer technique to verify if the structure is a palindrome. The first pointer starts at the beginning of the array, and the second starts at the end. If all elements from both ends are equal, then the list is a palindrome.
Steps:
- Traverse the linked list and store the values in an array.
- Use two pointers, one starting at the beginning of the array and the other at the end.
- Compare values at both pointers, move inward, and if all are equal, the list is a palindrome.
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the linked list.
- Space Complexity: O(n), for storing the values in a list.
2. Reverse Second Half in-place
Intuition:
A more optimized approach is to reverse the second half of the linked list and then compare it with the first half. If both halves are identical, then the linked list is a palindrome. This approach doesn't require extra space for storing values.
Steps:
- Find the midpoint of the linked list using the fast and slow pointer technique.
- Reverse the second half of the list.
- Compare the first half with the reversed second half.
- Restore the original list (optional).
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the linked list.
- Space Complexity: O(1), as we're changing the pointers in-place.