algoadvance

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Clarifying Questions

1. What is the expected input and output?
   • Input: The head of a singly linked list.
   • Output: A boolean value (True or False) indicating whether the linked list is a palindrome.
2. What is the range of input values?
   • The list can be empty or very large, up to the constraints of the problem’s definition.
3. Can we modify the linked list during the operations?
   • It is generally safer to assume that we should not modify the linked list unless explicitly allowed by the problem statement.

Strategy

1. Find the middle of the linked list.
   • Use the slow and fast pointer technique where the slow pointer moves one step at a time and the fast pointer moves two steps. When fast reaches the end, slow will reach the middle of the list.
2. Reverse the second half of the list.
   • Once the middle is found, reverse the second half of the linked list.
3. Check for palindrome.
   • Compare the elements from the start of the list and the start of the reversed second half.
4. Restore the list.
   • Optionally, restore the list back to its original state by reversing the second half again.
5. Return the result.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        
        # Function to reverse a linked list
        def reverse(head):
            prev = None
            current = head
            while current:
                next_node = current.next
                current.next = prev
                prev = current
                current = next_node
            return prev
        
        # Find the middle of the linked list
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Reverse the second half of the linked list
        second_half = reverse(slow)
        
        # Compare the first and second half nodes
        first_half, second_half_copy = head, second_half
        result = True
        while result and second_half_copy:
            if first_half.val != second_half_copy.val:
                result = False
            first_half = first_half.next
            second_half_copy = second_half_copy.next
        
        # Optional: Restore the list
        reverse(second_half)
        
        return result

Time Complexity

• Finding the middle of the linked list: O(n) where n is the number of nodes in the list.
• Reversing the second half of the linked list: O(n/2) which is simplified to O(n).
• Comparing the nodes: O(n/2) which is simplified to O(n).
• Restoring the list (optional): O(n/2) which is simplified to O(n).

Hence, the overall time complexity is O(n) since all operations contribute linearly.

Space Complexity

• The space complexity is O(1) as we are using only a few pointers, and no additional data structures that grow with the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?