Palindrome Linked List

📋

Problem

Imagine you have a chain of beads and want to check if the sequence of colors reads the same forwards and backwards without rearranging them.

Given the head of a singly linked list, determine if the linked list is a palindrome. Return true if it is, and false otherwise.

1 ≤ n ≤ 10^5Node values are integersExpected time complexity: O(n)Expected space complexity: O(1) or O(n) depending on approach

Edge cases: Single node list → trueList with all identical elements → trueList with two different elements → false

</>

IDE

def isPalindrome(head: Optional[ListNode]) -> bool:public boolean isPalindrome(ListNode head)bool isPalindrome(ListNode* head)function isPalindrome(head)

def isPalindrome(head):
    # Write your solution here
    pass

class Solution {
    public boolean isPalindrome(ListNode head) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isPalindrome(ListNode* head) {
    // Write your solution here
    return false;
}

function isPalindrome(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseIncorrectly returning false for palindrome lists due to incomplete pairwise comparison or incorrect reversal.✅ Ensure full two-pointer comparison from start and end; reverse second half correctly before comparison.

Wrong: trueReturning true for non-palindrome lists due to missing mismatch detection or partial reversal.✅ Return false immediately when a mismatch is found during comparison of halves.

Wrong: error or falseNot handling empty list or single node base cases properly, causing errors or wrong output.✅ Add base cases to return true if head is null or head.next is null.

Wrong: timeoutUsing inefficient approach like repeated list traversal or exponential time complexity.✅ Use fast and slow pointers with in-place reversal to achieve O(n) time complexity.

✓

Test Cases

Handle base cases like empty and single-node lists to avoid runtime errors.

Focus on correctly reversing the second half and comparing halves fully to catch subtle bugs.

Optimize your approach to O(n) time and O(1) space to handle large inputs efficiently.

t1_01basic

Input{"head":[1,2,2,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The list reads the same forwards and backwards.

💡 Try converting the linked list to an array and check if it reads the same forwards and backwards.

💡 Use two pointers to compare elements from start and end moving towards the center.

💡 Return false immediately if any pair of elements differ; otherwise return true.

Why it failed: Returned false for a palindrome list. Likely forgot to check all pairs or reversed incorrectly. Fix by ensuring full two-pointer comparison from both ends.

✓ Correctly identified the palindrome property using two-pointer or equivalent approach.

t1_02basic

Input{"head":[1,2,3,2,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The list reads the same forwards and backwards with an odd number of nodes.

💡 Consider the middle element in odd-length lists does not affect palindrome property.

💡 Use fast and slow pointers to find the middle, then compare halves.

💡 Reverse the second half and compare node values one by one.

Why it failed: Returned false for an odd-length palindrome. Possibly mishandled middle node or reversed half incorrectly. Fix by correctly identifying middle and comparing halves.

✓ Correctly handled odd-length palindrome by comparing halves properly.

t2_01edge

Input{"head":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

An empty list is trivially a palindrome.

💡 Check if the list is empty before processing.

💡 An empty list has no elements to compare, so it should return true.

💡 Return true immediately if head is null or None.

Why it failed: Returned false or error on empty list input. Fix by adding a base case to return true if head is null.

✓ Correctly returns true for empty list as palindrome.

t2_02edge

Input{"head":[1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

A single node list is always a palindrome.

💡 A single element list reads the same forwards and backwards.

💡 Check if head.next is null to identify single node.

💡 Return true immediately if only one node exists.

Why it failed: Returned false for single node list. Fix by adding base case to return true if head.next is null.

✓ Correctly returns true for single node list.

t2_03edge

Input{"head":[2,2,2,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

All identical elements form a palindrome.

💡 Check if all elements are the same; this is a palindrome.

💡 Two-pointer comparison should confirm all pairs are equal.

💡 No special handling needed; just ensure comparisons are correct.

Why it failed: Returned false for all identical elements. Possibly incorrect comparison logic. Fix by ensuring pairwise equality check is correct.

✓ Correctly identifies palindrome when all elements are identical.

t3_01corner

Input{"head":[1,2]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Two different elements list is not a palindrome.

💡 Check pairs from start and end carefully.

💡 Do not assume list length > 2 or that middle element exists.

💡 Return false as soon as a mismatch is found.

Why it failed: Returned true for non-palindrome two-element list. Likely missing early mismatch detection. Fix by returning false immediately on first unequal pair.

✓ Correctly returns false for two-element non-palindrome list.

t3_02corner

Input{"head":[1,2,3,4,2,1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

List that looks almost palindrome but is not due to one element mismatch.

💡 Check all pairs, not just first and last.

💡 Do not stop at middle if mismatch found earlier.

💡 Verify reversal and comparison logic carefully.

Why it failed: Returned true for non-palindrome list with subtle mismatch. Possibly incorrect reversal or comparison length. Fix by ensuring full half comparison.

✓ Correctly detects non-palindrome with subtle mismatch.

t3_03corner

Input{"head":[1,2,2,3]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 and unbounded knapsack analogy: partial reversal or incomplete comparison.

💡 Ensure you reverse exactly the second half of the list.

💡 Compare only the first half with reversed second half.

💡 Do not compare beyond the middle or miss nodes.

Why it failed: Returned true incorrectly due to partial or incorrect reversal/comparison. Fix by correctly finding middle and reversing second half fully.

✓ Correctly handles partial reversal and comparison for palindrome check.

t4_01performance

Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 nodes, O(n) time complexity expected to complete within 2 seconds.

💡 Use fast and slow pointers to find middle in O(n).

💡 Reverse second half in-place to keep O(1) space.

💡 Avoid converting list to array to prevent extra space/time overhead.

Why it failed: Solution timed out due to O(n^2) or exponential complexity. Fix by implementing O(n) time approach using fast-slow pointers and in-place reversal.

✓ Solution runs efficiently in O(n) time for large input.

Practice

1. You are given a circular array where each element represents a jump length and direction (positive for forward, negative for backward). The task is to determine if there exists a cycle in the array such that the cycle is longer than one element and all jumps are in the same direction. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to jump as far as possible from each index until a cycle is detected or no progress is made.

B. Dynamic programming to store reachable indices and detect cycles by memoization.

C. Brute force simulation from each index checking all possible cycles exhaustively.

D. Fast and slow pointer cycle detection that checks direction consistency and avoids single-element loops.

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify suitable algorithm

   Fast and slow pointer cycle detection efficiently finds cycles in O(n) time while checking direction and cycle length constraints.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast and slow pointers detect cycles without exhaustive search [OK]

Hint: Cycle detection with direction check -> fast-slow pointers [OK]

Common Mistakes:

• Assuming greedy jumps always find cycles
• Using DP which is inefficient here
• Brute force is correct but not optimal

2. What is the time complexity of the optimized fast and slow pointer approach for detecting a circular array loop in an array of length n?

medium

A. O(n^2) because each element may be visited multiple times

B. O(n log n) due to repeated modulo operations and pointer jumps

C. O(n) because each element is visited at most once due to marking visited elements

D. O(n) amortized but worst case can be O(n^2) if cycles overlap

Solution

1. Step 1: Identify outer loop and inner pointer movements

   The outer loop runs n times, but elements are marked zero once visited, preventing reprocessing.

2. Step 2: Analyze pointer visits

   Each element is visited at most once in the inner while loop due to zero marking, so total work is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Marking visited elements ensures linear time complexity [OK]

Hint: Marking visited elements prevents repeated work -> O(n) [OK]

Common Mistakes:

• Assuming repeated visits cause O(n^2)
• Confusing modulo cost as log factor
• Believing overlapping cycles increase complexity

3. What is the time complexity of the optimal Happy Number detection algorithm that uses a known cycle set and repeatedly computes the sum of squares of digits until it reaches 1 or a cycle number? Assume n is the input number and k is the number of iterations until termination.

medium

A. O(n) because each digit is processed once per iteration

B. O(k * log n) because each iteration processes digits proportional to log n and there are k iterations

C. O(k * n) because sum of squares depends on n itself

D. O(k) because the cycle detection set lookup is constant time and digits are fixed length

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits. Number of digits in n is proportional to log n, so each iteration is O(log n).

2. Step 2: Multiply by number of iterations k

   The process repeats k times until reaching 1 or cycle. Total time is O(k * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of digits per iteration is log n, repeated k times -> O(k * log n) [OK]

Hint: Sum of digits cost is O(log n), not O(n) [OK]

Common Mistakes:

• Confusing n with number of digits, assuming O(n) per iteration

4. Identify the bug in the following Python code for checking if a number is happy. The code attempts to detect cycles using recursion but lacks proper cycle detection.

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    def helper(num):
        if num == 1:
            return true
        return helper(get_next(num))

    return helper(n)

medium

A. Missing base case for cycle detection causing infinite recursion

B. Incorrect sum of squares calculation in get_next function

C. Returning helper(get_next(num)) without checking if num is 1

D. Not initializing total_sum to zero before summing digits

Solution

1. Step 1: Analyze recursion base cases

   The code only stops recursion if num == 1. It does not detect cycles, so for unhappy numbers it recurses infinitely.

2. Step 2: Identify missing cycle detection

   Without tracking visited numbers or using fast-slow pointers, the recursion never terminates for cycles, causing stack overflow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite recursion due to missing cycle detection base case [OK]

Hint: Check for cycle detection in recursion to avoid infinite loops [OK]

Common Mistakes:

• Assuming recursion stops at cycles without explicit detection

5. What is the time and space complexity of the optimal single-pass two-pointer approach to find the middle node of a singly linked list with n nodes?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(log n), Space: O(1)

Solution

1. Step 1: Identify time complexity

   Fast pointer moves two steps per iteration, slow moves one; total iterations proportional to n -> O(n) time.

2. Step 2: Identify space complexity

   Only two pointers used, no extra data structures -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for two-pointer traversal [OK]

Hint: Two pointers traverse list once, no extra storage [OK]

Common Mistakes:

• Confusing space with O(n) due to recursion
• Assuming nested loops cause O(n^2)
• Thinking fast pointer halves complexity to O(log n)