Nth Node from End of List (Return Value)

🎯

Nth Node from End of List (Return Value)

easyTWO_POINTERAmazonBloomberg

Imagine you are tracking the position of a train car from the end of a long train without counting all cars twice.

💡 This problem is about finding a specific node counting from the end of a singly linked list. Beginners often struggle because singly linked lists only allow forward traversal, so counting backwards is not straightforward without extra passes or memory.

📋

Problem Statement

Given the head of a singly linked list and an integer n, return the value of the nth node from the end of the list. If the list has fewer than n nodes, return null or an equivalent indication.

1 ≤ n ≤ 10^5The number of nodes in the list is at least 1Node values can be any integer

💡

Example

Input"head = [10 -> 20 -> 30 -> 40 -> 50], n = 2"

Output40

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

• n equals the length of the list → returns the head node's value
• n is 1 → returns the last node's value
• n is greater than the length of the list → returns null
• list has only one node and n is 1 → returns that node's value

⚠️

Common Mistakes

Not checking if n is larger than list length

Code crashes with null pointer exception or returns wrong value

✅ Add validation after counting length or during pointer advancement

Advancing fast pointer less than n steps

Slow pointer ends up at wrong node, incorrect output

✅ Ensure fast pointer moves exactly n steps before moving both pointers

Returning slow pointer instead of its value

Interviewers expect the value, returning node reference may cause confusion

✅ Return slow.val or equivalent

Using two passes but forgetting zero-based indexing adjustments

Off-by-one errors leading to wrong node selection

✅ Carefully calculate target index as length - n

🧠

Brute Force (Two Pass Traversal)

💡 This approach is the most straightforward and helps beginners understand the problem by first counting the list length, then accessing the target node. It lays the foundation for more efficient methods.

Intuition

First, find the total length of the list by traversing it once. Then, calculate the position of the target node from the start as length - n + 1, and traverse again to that node.

Algorithm

1. Traverse the list to count the total number of nodes.
2. Calculate the target index from the start as length - n.
3. Traverse the list again to the target index.
4. Return the value of the node at the target index or null if out of bounds.

💡 The two traversals are separate and easy to understand but inefficient because we scan the list twice.

</>

Code

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

def nth_from_end(head, n):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    if n > length:
        return None
    current = head
    for _ in range(length - n):
        current = current.next
    return current.val

# Example usage:
if __name__ == '__main__':
    # Create linked list 10->20->30->40->50
    head = ListNode(10, ListNode(20, ListNode(30, ListNode(40, ListNode(50)))))
    print(nth_from_end(head, 2))  # Output: 40

Line Notes

length = 0Initialize length counter to zero before traversal

while current:Traverse the entire list to count nodes

if n > length:Check if n is valid relative to list length

for _ in range(length - n):Traverse again to the (length - n)th node from start

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static Integer nthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        if (n > length) return null;
        current = head;
        for (int i = 0; i < length - n; i++) {
            current = current.next;
        }
        return current.val;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        head.next = new ListNode(20);
        head.next.next = new ListNode(30);
        head.next.next.next = new ListNode(40);
        head.next.next.next.next = new ListNode(50);
        System.out.println(nthFromEnd(head, 2)); // Output: 40
    }
}

Line Notes

int length = 0;Initialize length counter before first traversal

while (current != null)Count nodes by traversing the list

if (n > length) return null;Validate n against list length

for (int i = 0; i < length - n; i++)Traverse to the target node from the start

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int nthFromEnd(ListNode* head, int n) {
    int length = 0;
    ListNode* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    if (n > length) return -1; // Using -1 to indicate null
    current = head;
    for (int i = 0; i < length - n; i++) {
        current = current->next;
    }
    return current->val;
}

int main() {
    ListNode* head = new ListNode(10);
    head->next = new ListNode(20);
    head->next->next = new ListNode(30);
    head->next->next->next = new ListNode(40);
    head->next->next->next->next = new ListNode(50);
    cout << nthFromEnd(head, 2) << endl; // Output: 40
    return 0;
}

Line Notes

int length = 0;Initialize length counter before counting nodes

while (current != nullptr)Traverse list to find total length

if (n > length) return -1;Return sentinel if n is invalid

for (int i = 0; i < length - n; i++)Traverse to the target node from the front

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function nthFromEnd(head, n) {
    let length = 0;
    let current = head;
    while (current !== null) {
        length++;
        current = current.next;
    }
    if (n > length) return null;
    current = head;
    for (let i = 0; i < length - n; i++) {
        current = current.next;
    }
    return current.val;
}

// Example usage:
const head = new ListNode(10, new ListNode(20, new ListNode(30, new ListNode(40, new ListNode(50)))));
console.log(nthFromEnd(head, 2)); // Output: 40

Line Notes

let length = 0;Initialize counter for list length

while (current !== null)Count nodes by traversing list once

if (n > length) return null;Check if n is valid before second traversal

for (let i = 0; i < length - n; i++)Traverse to the target node from the start

⏱

Complexity

TimeO(2n) = O(n)

SpaceO(1)

We traverse the list twice: once to count length, once to find the target node. Both traversals are linear in n.

💡 For n=20, this means walking the list 40 steps total, which is inefficient but simple.

Interview Verdict: Accepted but not optimal

This approach works but is inefficient because it requires two passes over the list, which can be improved.

🧠

One Pass with Two Pointers (Fast and Slow)

💡 This approach introduces the fast-slow pointer technique, a fundamental pattern in linked list problems. It reduces the traversal to one pass, improving efficiency.

Intuition

Move a fast pointer n steps ahead first. Then move both fast and slow pointers together until fast reaches the end. Slow will then point to the nth node from the end.

Algorithm

1. Initialize two pointers, fast and slow, at the head.
2. Move fast pointer n steps ahead.
3. Move both pointers forward until fast reaches the end.
4. Slow pointer now points to the nth node from the end; return its value.

💡 The key is maintaining the gap of n between fast and slow pointers to find the target in one pass.

</>

Code

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

def nth_from_end(head, n):
    fast = slow = head
    for _ in range(n):
        if not fast:
            return None
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    return slow.val if slow else None

# Example usage:
if __name__ == '__main__':
    head = ListNode(10, ListNode(20, ListNode(30, ListNode(40, ListNode(50)))))
    print(nth_from_end(head, 2))  # Output: 40

Line Notes

fast = slow = headInitialize both pointers at the start

for _ in range(n):Advance fast pointer n steps ahead

if not fast:Check if n is larger than list length

while fast:Move both pointers until fast reaches the end

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static Integer nthFromEnd(ListNode head, int n) {
        ListNode fast = head, slow = head;
        for (int i = 0; i < n; i++) {
            if (fast == null) return null;
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow != null ? slow.val : null;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        head.next = new ListNode(20);
        head.next.next = new ListNode(30);
        head.next.next.next = new ListNode(40);
        head.next.next.next.next = new ListNode(50);
        System.out.println(nthFromEnd(head, 2)); // Output: 40
    }
}

Line Notes

ListNode fast = head, slow = head;Initialize two pointers at head

for (int i = 0; i < n; i++)Move fast pointer n steps ahead

if (fast == null) return null;Check if n exceeds list length

while (fast != null)Move both pointers until fast reaches end

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int nthFromEnd(ListNode* head, int n) {
    ListNode* fast = head;
    ListNode* slow = head;
    for (int i = 0; i < n; i++) {
        if (!fast) return -1;
        fast = fast->next;
    }
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow ? slow->val : -1;
}

int main() {
    ListNode* head = new ListNode(10);
    head->next = new ListNode(20);
    head->next->next = new ListNode(30);
    head->next->next->next = new ListNode(40);
    head->next->next->next->next = new ListNode(50);
    cout << nthFromEnd(head, 2) << endl; // Output: 40
    return 0;
}

Line Notes

ListNode* fast = head;Initialize fast pointer at head

for (int i = 0; i < n; i++)Advance fast pointer n steps

if (!fast) return -1;Return sentinel if n is invalid

while (fast)Move both pointers until fast reaches end

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function nthFromEnd(head, n) {
    let fast = head, slow = head;
    for (let i = 0; i < n; i++) {
        if (!fast) return null;
        fast = fast.next;
    }
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow ? slow.val : null;
}

// Example usage:
const head = new ListNode(10, new ListNode(20, new ListNode(30, new ListNode(40, new ListNode(50)))));
console.log(nthFromEnd(head, 2)); // Output: 40

Line Notes

let fast = head, slow = head;Initialize two pointers at head

for (let i = 0; i < n; i++)Advance fast pointer n steps ahead

if (!fast) return null;Check if n is larger than list length

while (fast)Move both pointers until fast reaches the end

⏱

Complexity

TimeO(n)

SpaceO(1)

Only one traversal of the list is needed, moving pointers in a single pass.

💡 For n=20, this means walking the list once (20 steps), which is twice as fast as the brute force.

Interview Verdict: Accepted and optimal for time

This is the preferred approach in interviews due to its efficiency and elegance.

🧠

Using Stack to Reverse Traverse

💡 This approach uses extra memory to simulate backward traversal by pushing nodes onto a stack. It is intuitive but less space efficient.

Intuition

Push all nodes onto a stack to reverse the traversal order. Then pop n nodes to reach the nth from the end.

Algorithm

1. Traverse the list and push all nodes onto a stack.
2. Pop n nodes from the stack.
3. The last popped node is the nth from the end; return its value.
4. If fewer than n nodes exist, return null.

💡 Using a stack reverses the traversal order, making it easy to access nodes from the end.

</>

Code

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

def nth_from_end(head, n):
    stack = []
    current = head
    while current:
        stack.append(current)
        current = current.next
    if n > len(stack):
        return None
    for _ in range(n - 1):
        stack.pop()
    return stack.pop().val

# Example usage:
if __name__ == '__main__':
    head = ListNode(10, ListNode(20, ListNode(30, ListNode(40, ListNode(50)))))
    print(nth_from_end(head, 2))  # Output: 40

Line Notes

stack = []Initialize stack to store nodes

while current:Traverse list and push nodes onto stack

if n > len(stack):Check if n is valid relative to stack size

for _ in range(n - 1):Pop n-1 nodes to reach nth from end

import java.util.Stack;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static Integer nthFromEnd(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<>();
        ListNode current = head;
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        if (n > stack.size()) return null;
        for (int i = 0; i < n - 1; i++) {
            stack.pop();
        }
        return stack.pop().val;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        head.next = new ListNode(20);
        head.next.next = new ListNode(30);
        head.next.next.next = new ListNode(40);
        head.next.next.next.next = new ListNode(50);
        System.out.println(nthFromEnd(head, 2)); // Output: 40
    }
}

Line Notes

Stack<ListNode> stack = new Stack<>();Initialize stack to hold nodes

while (current != null)Push all nodes onto stack

if (n > stack.size()) return null;Validate n against stack size

for (int i = 0; i < n - 1; i++)Pop n-1 nodes to reach nth from end

#include <iostream>
#include <stack>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int nthFromEnd(ListNode* head, int n) {
    stack<ListNode*> stk;
    ListNode* current = head;
    while (current) {
        stk.push(current);
        current = current->next;
    }
    if (n > stk.size()) return -1;
    for (int i = 0; i < n - 1; i++) {
        stk.pop();
    }
    return stk.top()->val;
}

int main() {
    ListNode* head = new ListNode(10);
    head->next = new ListNode(20);
    head->next->next = new ListNode(30);
    head->next->next->next = new ListNode(40);
    head->next->next->next->next = new ListNode(50);
    cout << nthFromEnd(head, 2) << endl; // Output: 40
    return 0;
}

Line Notes

stack<ListNode*> stk;Stack to hold pointers to nodes

while (current) {Push all nodes onto stack

if (n > stk.size()) return -1;Check if n is valid

for (int i = 0; i < n - 1; i++)Pop n-1 nodes to reach nth from end

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function nthFromEnd(head, n) {
    const stack = [];
    let current = head;
    while (current !== null) {
        stack.push(current);
        current = current.next;
    }
    if (n > stack.length) return null;
    for (let i = 0; i < n - 1; i++) {
        stack.pop();
    }
    return stack.pop().val;
}

// Example usage:
const head = new ListNode(10, new ListNode(20, new ListNode(30, new ListNode(40, new ListNode(50)))));
console.log(nthFromEnd(head, 2)); // Output: 40

Line Notes

const stack = [];Initialize stack to store nodes

while (current !== null)Push all nodes onto stack

if (n > stack.length) return null;Validate n against stack size

for (let i = 0; i < n - 1; i++)Pop n-1 nodes to reach nth from end

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list once and store all nodes in a stack, which requires linear extra space.

💡 For n=20, this means storing 20 nodes in memory, which can be costly for large lists.

Interview Verdict: Accepted but uses extra space

This approach is easy to implement but not space efficient compared to the two-pointer method.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer one-pass approach is the best choice for 95% of interviews due to its optimal time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Two Pass)	O(n)	O(1)	No	N/A	Mention only - never code
2. One Pass Two Pointers	O(n)	O(1)	No	N/A	Code this approach
3. Using Stack	O(n)	O(n)	No	N/A	Mention as alternative if extra space allowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force two-pass approach to show understanding.Step 3: Optimize to the one-pass two-pointer approach and explain why it is better.Step 4: Optionally mention the stack approach as an alternative.Step 5: Code the optimal solution carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your ability to handle linked list traversal, optimize from naive to efficient solutions, and manage edge cases.

Common Follow-ups

• What if you need to remove the nth node from the end? → Use similar two-pointer technique with a dummy node.
• How to handle invalid n values? → Check length or pointer validity before proceeding.

💡 These follow-ups test your ability to adapt the pattern to related problems and handle input validation.

🔍

Pattern Recognition

When to Use

1) Asked to find kth element from end in a singly linked list, 2) Single pass preferred, 3) No backward traversal allowed, 4) Constraints allow O(1) space

Signature Phrases

nth node from endsingle traversalfast and slow pointers

NOT This Pattern When

Problems requiring random access or doubly linked list traversal are different patterns.

Similar Problems

Middle of the Linked List - similar two-pointer technique to find middle nodeRemove Nth Node From End of List - extension to remove instead of returnLinked List Cycle - uses fast and slow pointers to detect cycles

Practice

1. Given the following code snippet for detecting a circular array loop, what is the return value when the input is nums = [2, -1, 1, 2, 2]?

easy

A. True

B. False

C. Raises an IndexError

D. Infinite loop

Solution

1. Step 1: Trace first iteration starting at index 0

   nums[0]=2 (positive), direction is forward. slow and fast start at 0.

2. Step 2: Move slow and fast pointers

   slow moves to index (0+2)%5=2, fast moves two steps: first to 2, then to (2+1)%5=3. Both nums[2] and nums[3] are positive, direction consistent.

3. Step 3: Next iteration

   slow moves to (2+1)%5=3, fast moves two steps: from 3 to (3+2)%5=0, then from 0 to (0+2)%5=2. slow=3, fast=2, not equal yet.

4. Step 4: Next iteration

   slow moves to (3+2)%5=0, fast moves two steps: from 2 to (2+1)%5=3, then from 3 to (3+2)%5=0. slow=0, fast=0, pointers meet.

5. Step 5: Check cycle length

   Check if slow == next_index(slow): next_index(0) = 2, not equal, so cycle length > 1.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Cycle detected with consistent direction and length > 1 [OK]

Hint: Pointers meet at index 0 with valid cycle -> returns True [OK]

Common Mistakes:

• Confusing slow and fast pointer positions
• Ignoring direction check
• Mistaking single-element loop as valid

2. Consider the following Python code implementing the optimized fast-slow pointer approach for detecting a cycle in a circular array. Given the input nums = [2, -1, 1, 2, 2], what is the return value of the function circularArrayLoop(nums)?

easy

A. Raises an IndexError

B. false

C. true

D. Infinite loop

Solution

1. Step 1: Trace first iteration with i=0

   Start at index 0, direction is positive. Moves: 0->2->3->0 forms a cycle of length >1 with consistent direction.

2. Step 2: Detect cycle and return true

   Fast and slow pointers meet at index 0, cycle length >1, so function returns true.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detected correctly for input [2, -1, 1, 2, 2] [OK]

Hint: Trace fast and slow pointers until they meet [OK]

Common Mistakes:

• Confusing direction checks
• Missing cycle length 1 check
• Miscomputing next index modulo

3. You are given a singly linked list and an integer n. The task is to remove the n-th node from the end of the list in a single pass without using extra space for storing nodes. Which approach guarantees this optimal solution?

easy

A. Traverse the list twice: first to count nodes, second to remove the target node.

B. Sort the list first, then remove the node at position length - n.

C. Use two pointers with a fixed gap of n+1 nodes, moving together until the fast pointer reaches the end.

D. Use a dynamic programming approach to store intermediate results for each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing the n-th node from the end in one pass without extra storage.

2. Step 2: Identify the two-pointer technique for single-pass removal

   Using two pointers with a gap of n+1 nodes ensures the slow pointer stops just before the target node, allowing removal in one pass.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

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

Hint: Two pointers with gap n+1 enable single-pass removal [OK]

Common Mistakes:

• Using two passes instead of one
• Trying to sort the list which is unnecessary
• Confusing DP with linked list traversal

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)