234. Palindrome Linked List
Model: qwen2.5-coder:14b
Topics: Linked List,Two Pointers
FAANG asked: 1
Acceptance rate: 41.9%
Problem Breakdown
The problem asks us to determine if a singly linked list is a palindrome. A palindrome reads the same forwards and backwards. The input is the head of a singly linked list, and the output should be a boolean indicating whether the list is a palindrome or not.
Inputs:
head: The head node of a singly linked list.
Outputs:
- A boolean value (
trueorfalse) indicating if the linked list is a palindrome.
Implicit Constraints/Edge Cases:
- The list can have anywhere from 1 to 10^5 nodes.
- Node values are integers between 0 and 9, inclusive.
- Edge cases include:
- A single-node list (which is trivially a palindrome).
- An empty list (though the problem specifies at least one node, this could be an implicit consideration).
Intuition
A brute-force approach would involve converting the linked list into an array and then checking if the array is a palindrome. This approach has a time complexity of O(n) due to the traversal needed to convert the list to an array and another O(n) for checking the palindrome, resulting in O(2n) or simply O(n). However, it uses additional space proportional to the number of nodes (O(n)) because we store all node values in an array.
A more efficient approach is to use two pointers to find the middle of the linked list and then reverse the second half of the list. This allows us to compare the first half with the reversed second half directly, achieving O(n) time complexity and O(1) space complexity.
Approach
- Find the Middle of the List: Use the slow and fast pointer technique where one pointer moves twice as fast as the other. When the fast pointer reaches the end, the slow pointer will be at the middle.
- Reverse the Second Half: Starting from the middle, reverse the second half of the list.
- Compare the Two Halves: Compare the values of nodes in the first half with the reversed second half.
- Restore the List (Optional): If needed, restore the original list by reversing the second half again.
- Return Result: Return
trueif all corresponding nodes match; otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(n) because we traverse the list a constant number of times (to find the middle, reverse the second half, and compare).
- Space Complexity: O(1) as we only use a few extra pointers regardless of the input size.
Solution
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head: ListNode) -> bool:
# Step 1: Find the middle of the list using slow and fast pointers
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse the second half of the list
prev = None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
# Step 3: Compare the first half and the reversed second half
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
# Step 4: Restore the list (optional)
# Reverse the second half again to restore the original list structure
prev = None
while prev is not head:
next_node = head.next
head.next = prev
prev = head
head = next_node
return True
Edge Cases Handled
- Single Node: The list is trivially a palindrome.
- Two Nodes: Compares the two nodes directly.
- Odd Length List: The middle node is ignored in comparison.
- Even Length List: Both halves are of equal length and compared directly.