Detect palindrome in linked list

Question

Given a singly linked list, write a function to determine if the list is a palindrome. A linked list is considered a palindrome if the sequence of values from the head to the tail is the same as the sequence from the tail to the head. The function should return a boolean value: true if the linked list is a palindrome, and false otherwise.

Codemia · Accepted Answer

To determine if a singly linked list is a palindrome, we can leverage the two-pointer technique. This technique allows us to find the midpoint of the linked list efficiently while simultaneously checking for symmetry. Specifically, we can use a fast and slow pointer approach: the slow pointer will move one step at a time, while the fast pointer moves two steps. This way, when the fast pointer reaches the end, the slow pointer will be at the midpoint. This method fits well here because it enables us to traverse the list in a single pass to find the midpoint, which is crucial for our palindrome check.

1. **Find the Midpoint**: Use the slow and fast pointer technique to find the midpoint of the linked list. For example, for the list `1 -> 2 -> 3 -> 2 -> 1`, the slow pointer will end at `3`.
2. **Reverse the Second Half**: Once the midpoint is located, reverse the second half of the linked list. The original list `2 -> 1` will become `1 -> 2`.
3. **Compare Both Halves**: Start from the head and the head of the reversed second half and compare the nodes. If all corresponding nodes match, the linked list is a palindrome. For our example, comparing `1` with `1` and `2` with `2` confirms that it is a palindrome.

Here’s the Python code implementing the above approach:
```python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

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

# Step 1: Find the midpoint
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

# Step 2: Reverse the second half
        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

# Step 3: Compare both halves
        left, right = head, prev
        while right:  # no need to check left half length
            if left.value != right.value:
                return False
            left = left.next
            right = right.next

return True
```

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because we traverse the list a constant number of times (finding the midpoint, reversing the second half, and comparing both halves). The space complexity is O(1) as we're only using a fixed amount of additional space regardless of the input size.

1. **Empty List**: An empty linked list should return `True` since there are no elements to contradict the palindrome property.
2. **Single Node List**: A list with a single node (e.g., `1`) should return `True` as it reads the same forwards and backwards.
3. **Two Different Nodes**: A list with two different nodes (e.g., `1 -> 2`) should return `False` as it is not a palindrome.
4. **Two Identical Nodes**: A list with two identical nodes (e.g., `1 -> 1`) should return `True`.
5. **Longer Palindrome**: A longer list that is a palindrome (e.g., `1 -> 2 -> 3 -> 2 -> 1`) should return `True`.

Detect palindrome in linked list

Zoom

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Zoom Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string