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

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

5. Suppose the array can contain multiple duplicates and some numbers appear more than twice. Which modification to Floyd's cycle detection algorithm correctly finds any duplicate number?

hard

A. No modification needed; Floyd's algorithm works regardless of duplicate count

B. Use a hash set to track visited numbers instead of cycle detection

C. Run Floyd's algorithm multiple times, removing found duplicates each time

D. Floyd's algorithm still works because the cycle corresponds to any duplicate, even if repeated

Solution

1. Step 1: Understand Floyd's algorithm behavior with multiple duplicates

   The cycle in the array corresponds to the repeated number's indices. Even if duplicates appear multiple times, the cycle exists and Floyd's algorithm detects its entrance.

2. Step 2: Confirm no need for multiple runs or extra data structures

   Floyd's algorithm finds one duplicate per run. It does not require modification to detect duplicates repeated more than twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection finds the cycle entrance regardless of duplicate frequency [OK]

Hint: Cycle entrance corresponds to duplicate regardless of count [OK]

Common Mistakes:

• Assuming Floyd's algorithm only works if duplicate appears twice
• Thinking multiple runs or extra space are needed
• Confusing cycle detection with hash-based methods