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 need to find the value of the node that is n positions from the end in a singly linked list. Which approach guarantees a single-pass solution with O(n) time complexity and O(1) extra space?

easy

A. Using a stack to store all nodes and then popping n times to get the target node.

B. Using two pointers where the fast pointer advances n steps ahead, then both move until fast reaches the end.

C. Calculating the length of the list first, then traversing again to the (length - n)th node.

D. Using a recursive function to traverse to the end and count back to the nth node.

Solution

1. Step 1: Understand the problem constraints

   The goal is to find the nth node from the end in a single pass with minimal extra space.

2. Step 2: Evaluate approaches

   Using two pointers with the fast pointer n steps ahead allows the slow pointer to land exactly on the target node when fast reaches the end, achieving O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer technique is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n solve in one pass [OK]

Common Mistakes:

• Confusing stack approach as single pass
• Using two passes instead of one
• Assuming recursion is O(1) space

2. You are given a singly linked list and asked to reorder it so that the nodes are arranged in the order: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal in-place solution with O(n) time and O(1) extra space?

easy

A. Use a brute force approach by storing all nodes in an array and then rearranging pointers.

B. Use dynamic programming to store intermediate reorder states and build the final list.

C. Recursively reorder the list by traversing to the end and merging nodes from both ends.

D. Find the middle of the list using fast and slow pointers, reverse the second half, then merge the two halves.

Solution

1. Step 1: Identify the problem constraints

   The problem requires reordering the list in-place with O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Brute force uses extra space, recursion uses O(n) stack space, and DP is not applicable here. The fast-slow pointer approach finds the middle, reverses the second half, and merges in-place efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast-slow pointer approach is classic for in-place reorder [OK]

Hint: Fast-slow pointer + reverse + merge is classic in-place reorder [OK]

Common Mistakes:

• Thinking recursion is O(1) space
• Using DP for linked list reorder
• Assuming array storage is in-place

3. Suppose the problem is modified so that the array elements can be zero, representing no movement, and cycles of length 1 (self-loop) are now considered valid. Which modification to the original fast and slow pointer algorithm correctly handles this variant?

hard

A. Remove the check that breaks when slow == next_index(slow), allowing single-element loops to return True.

B. Add a condition to skip zeros in the outer loop and treat zero jumps as invalid for cycles.

C. Modify the direction check to allow zero as both positive and negative direction to include zero jumps.

D. Use a visited set to track indices and return True if any index is revisited, ignoring direction.

Solution

1. Step 1: Understand new problem constraints

   Zero jumps are allowed and single-element loops are valid cycles.

2. Step 2: Identify necessary algorithm change

   The original code breaks when slow == next_index(slow) to exclude single-element loops; removing this check allows detecting single-element cycles.

3. Step 3: Confirm direction and zero handling

   Zeros represent no movement; allowing them means direction check must still be consistent, but zero jumps can form valid cycles.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing single-element loop break correctly detects new valid cycles [OK]

Hint: Allow single-element loops by removing cycle length >1 check [OK]

Common Mistakes:

• Skipping zeros entirely
• Treating zero as both directions
• Ignoring direction consistency

4. Suppose the linked list can have multiple cycles due to node reuse (e.g., a node's next pointer can point to any previously visited node, creating multiple cycle entries). Which modification to Floyd's algorithm correctly detects the first cycle start node encountered from the head?

hard

A. Run Floyd's algorithm repeatedly after removing detected cycles until no cycle remains.

B. Use two pointers but move fast pointer three steps at a time to detect multiple cycles faster.

C. Modify Floyd's algorithm to reset the fast pointer to head after detection and continue until slow and fast meet again.

D. Use a hash set to track visited nodes and return the first repeated node encountered during traversal.

Solution

1. Step 1: Understand multiple cycles scenario

   Floyd's algorithm assumes a single cycle; multiple cycles break its assumptions and can cause incorrect detection.

2. Step 2: Use hash set to detect first repeated node

   Tracking visited nodes with a hash set detects the first node that appears twice, correctly identifying the earliest cycle entry.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash set approach works correctly with multiple cycles but uses extra space [OK]

Hint: Floyd's algorithm fails with multiple cycles; hash set detects first repeated node [OK]

Common Mistakes:

• Trying to adapt Floyd's algorithm without extra space
• Assuming multiple cycles can't exist
• Increasing fast pointer speed doesn't help

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow