Difficulty: Easy | Acceptance: 57.90% | Paid: No Topics: Linked List, Two Pointers, Stack, Recursion
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Could you do it in O(n) time and O(1) space?
- Examples
- Constraints
- Approach 1: Copy to Array
- Approach 2: Stack
- Approach 3: Recursion
- Approach 4: Reverse Second Half
Examples
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Constraints
The number of nodes in the list is in the range [1, 10⁵].
0 <= Node.val <= 9
Approach 1: Copy to Array
Intuition Copy all the values from the linked list into an array. Checking if an array is a palindrome is straightforward using two pointers.
Steps
- Initialize an empty list/array.
- Traverse the linked list, appending each node’s value to the array.
- Use two pointers (one at the start, one at the end) to compare values moving towards the center.
- If any pair doesn’t match, return false. Otherwise, return true.
python
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
vals = []
current_node = head
while current_node is not None:
vals.append(current_node.val)
current_node = current_node.next
return vals == vals[::-1]Complexity
- Time: O(n)
- Space: O(n)
- Notes: Requires extra space proportional to the list size.
Approach 2: Stack
Intuition Use a stack to reverse the order of elements. Traverse the list once to push values onto the stack, then traverse again to compare with popped values (which are in reverse order).
Steps
- Initialize an empty stack.
- Traverse the linked list, pushing each node’s value onto the stack.
- Traverse the linked list again. For each node, pop a value from the stack and compare it with the node’s value.
- If any mismatch occurs, return false. If the loop finishes, return true.
python
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
stack = []
current_node = head
while current_node is not None:
stack.append(current_node.val)
current_node = current_node.next
current_node = head
while current_node is not None:
if current_node.val != stack.pop():
return False
current_node = current_node.next
return TrueComplexity
- Time: O(n)
- Space: O(n)
- Notes: Uses stack memory proportional to the list size.
Approach 3: Recursion
Intuition Use the system’s call stack to simulate the reversal process. Recurse to the end of the list, and as the recursion unwinds, compare the current node with the front node moving forward.
Steps
- Maintain a global or class-level pointer to the head of the list (front pointer).
- Define a recursive function that takes a node.
- Recursively call the function until the end of the list is reached.
- On the way back (unwinding), compare the current node’s value with the front pointer’s value.
- Advance the front pointer. Return true if all comparisons match.
python
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
self.front_pointer = head
def recursively_check(current_node):
if current_node is not None:
if not recursively_check(current_node.next):
return False
if current_node.val != self.front_pointer.val:
return False
self.front_pointer = self.front_pointer.next
return True
return recursively_check(head)Complexity
- Time: O(n)
- Space: O(n)
- Notes: Uses implicit stack space due to recursion depth.
Approach 4: Reverse Second Half
Intuition Optimize space to O(1) by reversing the second half of the linked list in place. Then compare the first half with the reversed second half.
Steps
- Find the end of the first half using the slow/fast pointer technique.
- Reverse the second half of the list.
- Compare the first half and the reversed second half node by node.
- (Optional) Reverse the second half again to restore the original list structure.
- Return the result of the comparison.
python
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if head is None:
return True
# Find the end of the first half
first_half_end = self.end_of_first_half(head)
# Reverse the second half
second_half_start = self.reverse_list(first_half_end.next)
# Check whether or not it is a palindrome
p1 = head
p2 = second_half_start
result = True
while result and p2 is not None:
if p1.val != p2.val:
result = False
p1 = p1.next
p2 = p2.next
# Restore the list (optional)
first_half_end.next = self.reverse_list(second_half_start)
return result
def end_of_first_half(self, head):
fast = head
slow = head
while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
return slow
def reverse_list(self, head):
prev = None
curr = head
while curr is not None:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prevComplexity
- Time: O(n)
- Space: O(1)
- Notes: Modifies the list in place but uses constant extra space.