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 two non-empty singly linked lists representing two non-negative integers. The digits are stored in forward order, with the most significant digit at the head. You need to add the two numbers and return the sum as a linked list in the same forward order. Which approach guarantees an optimal solution without modifying the input lists or using extra space proportional to the number of digits?

easy

A. Reverse both lists, add digits from least significant to most significant, then reverse the result.

B. Use a greedy approach to add digits from left to right without padding or recursion.

C. Pad the shorter list with zeros, recursively add corresponding nodes from the most significant digit, and propagate carry backward.

D. Convert both lists to integers, add them, then convert the sum back to a linked list.

Solution

1. Step 1: Understand the problem constraints

   The digits are stored in forward order, so addition must start from the most significant digit. Direct addition from head to tail requires alignment of list lengths.

2. Step 2: Identify the approach that handles alignment and carry correctly

   Padding the shorter list ensures both lists have equal length. Recursively adding nodes from the most significant digit allows carry to propagate backward naturally without reversing or extra space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Padding + recursion handles carry and alignment correctly [OK]

Hint: Pad shorter list and recurse from MSB [OK]

Common Mistakes:

• Reversing lists modifies inputs unexpectedly
• Greedy addition fails due to carry propagation
• Converting to integers causes overflow or inefficiency

2. Consider the following Python code for merging two sorted linked lists in-place:

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

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            l1 = l1.next
        prev.next = l2
        l1, l2 = l2, l1
    return head

# Input lists:
# l1: 1 -> 3 -> 5
# l2: 2 -> 4

merged_head = mergeTwoLists(l1, l2)

What is the value of the node pointed to by prev after the first inner while loop iteration inside the outer while loop?

easy

A. Node with value 3

B. Node with value 5

C. Node with value 1

D. Node with value 2

Solution

1. Step 1: Trace the inner while loop with initial lists

   Initially, l1 points to 1, l2 points to 2. The inner loop advances l1 while l1.val <= l2.val: - l1=1 (<=2), prev=1, l1 moves to 3 - l1=3 (>2), loop stops

2. Step 2: Identify prev after loop

   Prev points to node with value 1 after the inner loop ends, which is the last node with value less than or equal to l2.val.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Prev points to last l1 node ≤ current l2 node [OK]

Hint: Prev points to last l1 node ≤ current l2 node [OK]

Common Mistakes:

• Assuming prev points to node with value 3 after first inner loop
• Confusing l1 and l2 pointers after swap
• Forgetting that prev updates inside inner loop

3. You are given a singly linked list and asked to reverse it in-place, such that the last node becomes the head and all pointers are reversed. Which approach guarantees an optimal solution with O(n) time and O(n) space complexity, avoiding stack overflow on large inputs?

easy

A. Use a brute force recursive reversal that reverses pointers on the way back up the call stack.

B. Use dynamic programming to store reversed sublists and combine them to form the reversed list.

C. Use a greedy approach that swaps node values instead of pointers to reverse the list.

D. Use a tail-recursive helper function that passes previous and current nodes, reversing pointers during the recursive descent.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing a singly linked list in-place, which means changing the next pointers without extra data structures.

2. Step 2: Evaluate approaches

   The brute force recursive reversal (A) uses recursion but reverses pointers on the return path, risking stack overflow and extra space. The greedy approach (C) swaps values, which is not pointer reversal and may not be allowed. Dynamic programming (D) is not applicable here. The tail-recursive helper function (B) reverses pointers during recursion descent, maintaining O(n) time and O(n) space due to recursion stack, and is optimal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tail recursion with prev and curr pointers ensures correct reversal [OK]

Hint: Tail recursion reverses pointers during descent [OK]

Common Mistakes:

• Confusing value swapping with pointer reversal
• Using naive recursion causing stack overflow

4. Examine the following buggy code snippet from a bottom-up merge sort on a linked list. Which line contains the subtle bug that can cause infinite loops or incorrect merges?

medium

A. Line: right = split(left, size)

B. Line: tail.next = merged

C. Line: cur = split(right, size)

D. Line: while tail.next: tail = tail.next

Solution

1. Step 1: Understand tail pointer update

   After merging, tail must move to the end of merged list to link next merges correctly.

2. Step 2: Identify bug in tail advancement loop

   The loop 'while tail.next: tail = tail.next' moves tail forward, but if tail.next is null, loop stops. However, if tail.next is not updated properly or merged list ends with a cycle, this can cause infinite loop or skip last node.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect tail advancement causes malformed list or infinite loop [OK]

Hint: Tail pointer must advance exactly to merged list end [OK]

Common Mistakes:

• Not breaking list properly in split causing cycles
• Not updating tail after merge causing truncated list
• Incorrectly assigning right sublist in split

5. Suppose you want to modify the bottom-up merge sort on a linked list to handle the case where the list nodes can be reused multiple times (i.e., duplicates allowed and nodes can appear multiple times). Which modification is necessary to maintain correctness and efficiency?

hard

A. Add a hash set to track visited nodes during merge to prevent infinite loops caused by reuse.

B. No modification needed; the existing algorithm handles duplicates and reuse naturally.

C. Modify the merge function to create new nodes instead of reusing existing nodes to avoid cycles.

D. Switch to recursive merge sort to better handle node reuse and duplicates.

Solution

1. Step 1: Understand node reuse implications

   If nodes can be reused multiple times, re-linking existing nodes in merge can create cycles or corrupt list structure.

2. Step 2: Modify merge to create new nodes

   Creating new nodes during merge avoids modifying shared nodes, preventing cycles and preserving correctness.

3. Step 3: Evaluate other options

   Tracking visited nodes adds overhead and complexity; recursion does not solve reuse issues; no modification risks infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Creating new nodes ensures safe merges with reused nodes [OK]

Hint: Reusing nodes requires copying to avoid cycles [OK]

Common Mistakes:

• Assuming existing merge works with reused nodes
• Trying to detect cycles dynamically instead of preventing
• Switching to recursion without addressing reuse