Detect palindrome in linked list

Question

Given a singly linked list, write a function to determine if the linked 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 indicating whether the linked list is a palindrome.

Codemia · Accepted Answer

To determine if a singly linked list is a palindrome, we can leverage the two-pointer technique to find the middle of the list and then reverse the second half for comparison. The two-pointer approach is particularly apt here because we can traverse the list in a single pass to find the midpoint and then another pass to check for palindrome properties, minimizing our overall time complexity.

1. **Find the Middle of the List**: Use two pointers, `slow` and `fast`, where `slow` moves one step at a time and `fast` moves two steps. By the time `fast` reaches the end, `slow` will be at the midpoint. 
2. **Reverse the Second Half**: Once we have the midpoint, we can reverse the second half of the list starting from `slow`. 
3. **Compare the Two Halves**: Use another pointer to traverse from the head to the midpoint and compare values with the reversed second half. If at any point the values differ, we can conclude that the list is not a palindrome.

**Example**: For the linked list 1 -> 2 -> 3 -> 2 -> 1: 
- The slow pointer reaches the middle at 3. 
- The second half (2 -> 1) is reversed to 1 -> 2. 
- Comparing the first half (1 -> 2 -> 3) with the reversed second half (1 -> 2), we find that they match, confirming it is a palindrome.

```python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def is_palindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True  # An empty list or a single node is a palindrome.

# Step 1: Find the middle of the linked list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

# Step 2: Reverse the second half of the linked list
    prev = None
    while slow:
        temp = slow.next
        slow.next = prev
        prev = slow
        slow = temp

# Step 3: Compare the two halves
    left, right = head, prev
    while right:
        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 few times: once to find the middle, once to reverse the second half, and once to compare both halves. The space complexity is O(1) since we are not using any additional data structures that grow with the input size; we are merely manipulating pointers.

1. **Empty List**: An empty list should return True, as it trivially satisfies the palindrome condition.
2. **Single Node**: A list with one node should also return True.
3. **Two Identical Nodes**: A list with two identical nodes (e.g., 1 -> 1) should return True.
4. **Two Different Nodes**: A list with two different nodes (e.g., 1 -> 2) should return False. 
5. **Longer Odd and Even Lengths**: Testing lists with odd lengths (1 -> 2 -> 1) and even lengths (1 -> 2 -> 2 -> 1) to ensure both cases are correctly handled.

Detect palindrome in linked list

Instacart

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

Instacart 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