Jobs

Interviews

Discussions

Palindrome Linked List

Easy

Asked by:

More companies

24 views

Topics:

Linked ListsTwo Pointers

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]
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

Follow up: Could you do it in O(n) time and O(1) space?

Try coding it in LeetCode

Palindrome Linked List

Easy

Asked by:

More companies

24 views

Topics:

Linked ListsTwo Pointers

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]
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

Follow up: Could you do it in O(n) time and O(1) space?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain only one node?
What is the range of values stored in the nodes of the linked list?
Should I return `true` or `false` if the linked list is empty?
Is the linked list singly or doubly linked?
Are the values in the nodes integers, or could they be other data types (like strings or floats)?

Brute Force Solution

Approach

To check if a linked list is a palindrome using brute force, we essentially write down the list's values and then see if they read the same forwards and backward. We explore every possible way to verify this.

Here's how the algorithm would work step-by-step:

First, go through the entire linked list and copy all the values into a separate, simple list.
Now, check if the simple list is the same when read from the beginning to the end and from the end to the beginning.
To do this, compare the first value with the last value. Then, compare the second value with the second-to-last value, and so on.
Keep doing this until you reach the middle of the list.
If at any point two corresponding values are different, then the original linked list is not a palindrome.
If you reach the middle of the list and all the values have matched up until now, then the original linked list is a palindrome.

Code Implementation

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

def is_palindrome_brute_force(head):
    list_of_values = []

    current_node = head
    # Iterate through the linked list and store values in a list
    while current_node:
        list_of_values.append(current_node.val)
        current_node = current_node.next

    left_index = 0
    right_index = len(list_of_values) - 1

    # Iterate until the middle of the list is reached
    while left_index < right_index:
        # Compare values from both ends
        if list_of_values[left_index] != list_of_values[right_index]:
            # Values don't match, not a palindrome
            return False

        left_index += 1
        right_index -= 1

    # All values matched; it's a palindrome
    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once to copy the n values into an array. Then, it iterates through the array from both ends to compare elements, which takes at most n/2 comparisons. Therefore, the time complexity is dominated by the initial traversal and can be approximated as O(n + n/2), which simplifies to O(n).

Space Complexity

O(N) – The provided solution's space complexity stems from creating a separate simple list to store the values of the linked list. This list's size grows linearly with the number of nodes, N, in the original linked list, where N is the number of nodes in the linked list. Therefore, the auxiliary space required is proportional to the input size. Consequently, the space complexity is O(N).

Optimal Solution

Approach

To check if a linked list is a palindrome efficiently, we don't need to compare every single element. Instead, we can split the list in half, reverse the second half, and then compare the two halves to see if they match.

Here's how the algorithm would work step-by-step:

First, find the middle of the linked list.
Once you have the middle, reverse the second half of the linked list.
Now, compare the first half of the original list with the reversed second half. If they are identical, the linked list is a palindrome.
After comparison, you can reverse the second half again to restore the original linked list, if required.
By only reversing and comparing half of the list, we drastically reduce the amount of work needed.

Code Implementation

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

def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True

    # Find the middle of the linked list.
    slow_pointer = head
    fast_pointer = head
    while fast_pointer and fast_pointer.next:
        slow_pointer = slow_pointer.next
        fast_pointer = fast_pointer.next.next

    # Reverse the second half of the linked list.
    previous_node = None
    current_node = slow_pointer
    while current_node:
        next_node = current_node.next
        current_node.next = previous_node
        previous_node = current_node
        current_node = next_node

    # Compare the first half with the reversed second half.
    first_half_pointer = head
    second_half_pointer = previous_node
    while second_half_pointer:
        if first_half_pointer.val != second_half_pointer.val:
            return False
        first_half_pointer = first_half_pointer.next
        second_half_pointer = second_half_pointer.next

    return True

Big(O) Analysis

Time Complexity

O(n) – Finding the middle of the linked list requires traversing approximately n/2 nodes, which is O(n). Reversing the second half of the list also involves traversing approximately n/2 nodes, another O(n) operation. Finally, comparing the first half with the reversed second half takes about n/2 steps, contributing another O(n). Therefore, the dominant term is O(n), and the total time complexity is O(n).

Space Complexity

O(1) – The described algorithm primarily uses in-place operations. Reversing the second half of the linked list is done in-place, requiring only a few pointer variables. Similarly, comparing the two halves involves traversing existing nodes with a few pointer variables. Thus, the auxiliary space required remains constant regardless of the linked list's size (N), making it O(1).

Edge Cases

Case	How to Handle
Empty list	Return True immediately since an empty list is considered a palindrome.
Single node list	Return True immediately since a single node list is also considered a palindrome.
Two node list with same values	Return True as the list is a palindrome.
Two node list with different values	Return False as the list is not a palindrome.
List with a large number of nodes (memory constraints)	Iterative solutions using constant extra space are preferred for very large lists to avoid stack overflow or memory issues with recursive calls.
List with all nodes having the same value	Should return True as it is a palindrome, and algorithm needs to handle this without infinite loops or incorrect comparisons.
List with integer overflow potential (if comparing node values directly)	Avoid direct value comparison if overflow is a concern; compare structure (node references) or use a more robust method like converting to string.
List containing negative or zero values	The algorithm should correctly handle negative and zero values as palindrome checks are based on structure, not value ranges.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain only one node?
What is the range of values stored in the nodes of the linked list?
Should I return `true` or `false` if the linked list is empty?
Is the linked list singly or doubly linked?
Are the values in the nodes integers, or could they be other data types (like strings or floats)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, go through the entire linked list and copy all the values into a separate, simple list.
Now, check if the simple list is the same when read from the beginning to the end and from the end to the beginning.
To do this, compare the first value with the last value. Then, compare the second value with the second-to-last value, and so on.
Keep doing this until you reach the middle of the list.
If at any point two corresponding values are different, then the original linked list is not a palindrome.
If you reach the middle of the list and all the values have matched up until now, then the original linked list is a palindrome.

Code Implementation

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

def is_palindrome_brute_force(head):
    list_of_values = []

    current_node = head
    # Iterate through the linked list and store values in a list
    while current_node:
        list_of_values.append(current_node.val)
        current_node = current_node.next

    left_index = 0
    right_index = len(list_of_values) - 1

    # Iterate until the middle of the list is reached
    while left_index < right_index:
        # Compare values from both ends
        if list_of_values[left_index] != list_of_values[right_index]:
            # Values don't match, not a palindrome
            return False

        left_index += 1
        right_index -= 1

    # All values matched; it's a palindrome
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the middle of the linked list.
Once you have the middle, reverse the second half of the linked list.
Now, compare the first half of the original list with the reversed second half. If they are identical, the linked list is a palindrome.
After comparison, you can reverse the second half again to restore the original linked list, if required.
By only reversing and comparing half of the list, we drastically reduce the amount of work needed.

Code Implementation

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

def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True

    # Find the middle of the linked list.
    slow_pointer = head
    fast_pointer = head
    while fast_pointer and fast_pointer.next:
        slow_pointer = slow_pointer.next
        fast_pointer = fast_pointer.next.next

    # Reverse the second half of the linked list.
    previous_node = None
    current_node = slow_pointer
    while current_node:
        next_node = current_node.next
        current_node.next = previous_node
        previous_node = current_node
        current_node = next_node

    # Compare the first half with the reversed second half.
    first_half_pointer = head
    second_half_pointer = previous_node
    while second_half_pointer:
        if first_half_pointer.val != second_half_pointer.val:
            return False
        first_half_pointer = first_half_pointer.next
        second_half_pointer = second_half_pointer.next

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty list	Return True immediately since an empty list is considered a palindrome.
Single node list	Return True immediately since a single node list is also considered a palindrome.
Two node list with same values	Return True as the list is a palindrome.
Two node list with different values	Return False as the list is not a palindrome.
List with a large number of nodes (memory constraints)	Iterative solutions using constant extra space are preferred for very large lists to avoid stack overflow or memory issues with recursive calls.
List with all nodes having the same value	Should return True as it is a palindrome, and algorithm needs to handle this without infinite loops or incorrect comparisons.
List with integer overflow potential (if comparing node values directly)	Avoid direct value comparison if overflow is a concern; compare structure (node references) or use a more robust method like converting to string.
List containing negative or zero values	The algorithm should correctly handle negative and zero values as palindrome checks are based on structure, not value ranges.