Nth Node from End of List (Return Value)

📋

Nth Node from End of List (Return Value)

Edge cases:

</>

IDE

def nth_from_end(head: ListNode, n: int) -> int | None:public Integer nthFromEnd(ListNode head, int n)int nthFromEnd(ListNode* head, int n)function nthFromEnd(head, n)

def nth_from_end(head, n):
    # Write your solution here
    pass

class Solution {
    public Integer nthFromEnd(ListNode head, int n) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

int nthFromEnd(ListNode* head, int n) {
    // Write your solution here
    return -1;
}

function nthFromEnd(head, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: None when n is validDid not move fast pointer n steps before moving slow pointer, causing early termination.✅ Move fast pointer exactly n steps before moving slow pointer.

Wrong: Value of wrong node (e.g., head instead of nth from end)Off-by-one error in pointer movement or indexing confusion.✅ Ensure fast pointer moves n steps and slow pointer moves until fast reaches end; return slow.val.

Wrong: Non-null value when n > list lengthDid not check if fast pointer can move n steps; no null return for invalid n.✅ Return null if fast pointer cannot move n steps.

Wrong: Wrong value due to moving slow pointer too earlyGreedy approach moving slow pointer before fast pointer moves n steps.✅ Move fast pointer n steps first, then move slow and fast pointers together.

Wrong: Timeout or no outputUsing nested loops or multiple passes causing O(n^2) complexity.✅ Use two-pointer single pass approach for O(n) time complexity.

✓

Test Cases

Review how your code handles lists with length equal to or less than n.

Check pointer movement carefully to avoid off-by-one and greedy mistakes.

Focus on optimizing your solution to run in linear time with constant space.

t1_01basic

Input{"head":[10,20,30,40,50],"n":2}

Expected40

⏱ Performance - must finish in 2000ms

The 2nd node from the end is the node with value 40.

💡 Use two pointers separated by n nodes to find the target node in one pass.

💡 Advance the fast pointer n steps first, then move both pointers until fast reaches the end.

💡 Return the slow pointer's node value after fast pointer reaches the list end.

Why it failed: Returned wrong value or None for a valid n; likely did not advance fast pointer n steps before moving slow. Fix by ensuring fast pointer moves n steps first.

✓ Correctly found the nth node from the end using two-pointer technique.

t1_02basic

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

Expected3

⏱ Performance - must finish in 2000ms

The 4th node from the end is the node with value 3.

💡 Remember to handle the case when n is less than the list length.

💡 Use the fast pointer to move n steps ahead before moving both pointers.

💡 Return the slow pointer's value after fast pointer reaches the end.

Why it failed: Returned wrong node value or None; possibly did not correctly handle the offset of n steps. Fix by moving fast pointer exactly n steps before moving slow.

✓ Correctly identified the 4th node from the end.

t2_01edge

Input{"head":[5],"n":1}

Expected5

⏱ Performance - must finish in 2000ms

Single node list with n=1 returns the only node's value.

💡 Check behavior when list has only one node.

💡 Ensure your code returns the head node's value when n=1 and list length=1.

💡 Return head.val if n equals list length.

Why it failed: Returned None or error for single node list with n=1; fix by handling single node case explicitly or ensuring two-pointer logic works when fast pointer moves n steps.

✓ Correctly handled single node list with n=1.

t2_02edge

Input{"head":[10,20,30],"n":3}

Expected10

⏱ Performance - must finish in 2000ms

n equals list length returns the head node's value.

💡 Test when n equals the length of the list.

💡 Fast pointer moves exactly n steps to reach null, slow pointer should be at head.

💡 Return slow pointer's value after fast pointer reaches the end.

Why it failed: Returned wrong value or None when n equals list length; fix by allowing fast pointer to move n steps and returning slow pointer's value.

✓ Correctly returned head node's value when n equals list length.

t2_03edge

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

Expectednull

⏱ Performance - must finish in 2000ms

n greater than list length returns null.

💡 Check if n is greater than the list length before proceeding.

💡 If fast pointer cannot move n steps, return null.

💡 Return null when n exceeds list length.

Why it failed: Returned a node value instead of null when n > list length; fix by checking if fast pointer can move n steps and return null if not.

✓ Correctly returned null when n is greater than list length.

t2_04edge

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

Expectednull

⏱ Performance - must finish in 2000ms

Empty list returns null regardless of n.

💡 Check for empty list input.

💡 Return null immediately if head is null.

💡 No nodes means no nth from end.

Why it failed: Did not handle empty list input; fix by returning null if head is null.

✓ Correctly returned null for empty list.

t3_01corner

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

Expected5

⏱ Performance - must finish in 2000ms

Returns last node's value; tests off-by-one errors in pointer movement.

💡 Check if your pointers correctly identify the last node when n=1.

💡 Ensure fast pointer moves n steps and slow pointer moves until fast reaches end.

💡 Return slow pointer's value after fast pointer reaches null.

Why it failed: Returned wrong value for n=1; likely off-by-one error in pointer movement. Fix by moving fast pointer n steps before moving slow pointer.

✓ Correctly returned last node's value for n=1.

t3_02corner

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

Expected1

⏱ Performance - must finish in 2000ms

Tests confusion between 0-based and 1-based indexing for n equal to list length.

💡 Verify indexing logic when n equals list length.

💡 Fast pointer should move n steps to null, slow pointer at head.

💡 Return slow pointer's value after fast pointer reaches null.

Why it failed: Returned wrong node or None for n equal to list length; fix by correctly moving fast pointer n steps and returning slow pointer's value.

✓ Correctly handled n equal to list length indexing.

t3_03corner

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

Expected3

⏱ Performance - must finish in 2000ms

Tests common greedy trap: moving slow pointer too early or late.

💡 Ensure fast pointer moves n steps before moving slow pointer.

💡 Do not move slow pointer until fast pointer has advanced n nodes.

💡 Return slow pointer's value after fast pointer reaches end.

Why it failed: Returned wrong value due to moving slow pointer before fast pointer moved n steps; fix by moving fast pointer n steps first.

✓ Correctly avoided greedy trap by proper pointer movement.

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],"n":50}

Expectednull

⏱ Performance - must finish in 2000ms

n=50, list length=100; solution must run in O(n) time within 2 seconds.

💡 Use two pointers to achieve one pass O(n) time complexity.

💡 Avoid nested loops or multiple traversals.

💡 Do not use extra space proportional to n.

Why it failed: Solution timed out due to O(n^2) or exponential complexity; fix by implementing single pass two-pointer approach.

✓ Solution runs in O(n) time confirming efficient complexity.

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. You are given a singly linked list and need to determine the length of a cycle if one exists. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use dynamic programming to store cycle lengths for sublists and combine results.

B. Use a hash set to store visited nodes and count cycle length upon revisiting a node.

C. Use two pointers moving at different speeds to detect the cycle and then count its length by traversing the cycle once.

D. Use a recursive depth-first search to detect cycles and count their lengths.

Solution

1. Step 1: Understand the problem constraints

   The problem requires detecting a cycle and counting its length efficiently in a linked list.

2. Step 2: Evaluate approaches for time and space complexity

   Using two pointers (fast and slow) allows cycle detection in O(n) time and O(1) space, then counting the cycle length by traversing the cycle once is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Fast-slow pointer approach is classic for cycle detection with constant space [OK]

Hint: Fast-slow pointers detect cycles in O(1) space [OK]

Common Mistakes:

• Believing hash sets are optimal due to extra space
• Confusing DP with cycle detection
• Using recursion unnecessarily

3. Consider the following buggy code snippet for detecting a circular array loop. Which line contains the subtle bug that causes incorrect detection of single-element loops as valid cycles?

medium

A. Line with 'if nums[i] == 0: continue' - skipping zeros prematurely

B. Line with 'if slow == fast: return True' - missing check for single-element loop

C. Line with 'direction = nums[i] > 0' - direction assignment incorrect

D. Line with 'nums[slow] = 0' - zeroing visited elements too early

Solution

1. Step 1: Identify where single-element loops are checked

   The original code breaks if slow == next_index(slow) to avoid single-element loops.

2. Step 2: Locate missing check

   The buggy code returns True immediately when slow == fast without verifying cycle length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing single-element loop check causes false positives [OK]

Hint: Check cycle length before returning True to avoid single-element loops [OK]

Common Mistakes:

• Returning True immediately on pointer meet
• Ignoring direction consistency
• Incorrectly zeroing elements

4. 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

5. The following code attempts to remove the nth node from the end of a singly linked list. Identify the line containing the subtle bug that causes incorrect behavior when removing the head node.

medium

A. Line 12: recurse(head)

B. Line 9: node.next = node.next.next

C. Line 3: def recurse(node):

D. Line 13: return head

Solution

1. Step 1: Understand dummy node role

   Dummy node is needed to handle removal of the head node safely.

2. Step 2: Identify missing dummy usage

   Calling recurse on head directly skips dummy, so removing head node breaks list or returns wrong head.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dummy node causes incorrect removal of head [OK]

Hint: Always use dummy node to handle head removal edge case [OK]

Common Mistakes:

• Not using dummy node causing null pointer or wrong head
• Incorrectly unlinking nodes causing list corruption
• Off-by-one errors in recursion index