Nth Node from End of List (Return Value)

▶

Steps

setup

Initialize pointers and stack

We start with the head of the list pointing to the first node (value 10). The stack is empty, and the current pointer is set to head to begin traversal.

💡 Setting up the current pointer and empty stack is essential to start traversing the list and collecting nodes.

Line:

stack = []
current = head

💡 The current pointer will move through the list to push all nodes onto the stack.

fill_row

Push node 10 onto stack

The current node (value 10) is pushed onto the stack. Then, current moves to the next node (value 20).

💡 Pushing nodes onto the stack reverses the traversal order, enabling us to access nodes from the end later.

Line:

stack.append(current)
current = current.next

💡 Stack now contains node 10; current moves forward to continue traversal.

fill_row

Push node 20 onto stack

Current node (value 20) is pushed onto the stack. Current advances to node 30.

💡 Each push adds the current node to the stack, building the reversed order.

Line:

stack.append(current)
current = current.next

💡 Stack now contains nodes 10 and 20, with 20 on top.

fill_row

Push node 30 onto stack

Current node (value 30) is pushed onto the stack. Current moves to node 40.

💡 Continuing to push nodes onto the stack to reverse the list order.

Line:

stack.append(current)
current = current.next

💡 Stack now has nodes 10, 20, 30 with 30 on top.

fill_row

Push node 40 onto stack

Current node (value 40) is pushed onto the stack. Current moves to node 50.

💡 Adding the second last node to the stack to prepare for popping.

Line:

stack.append(current)
current = current.next

💡 Stack now contains nodes 10, 20, 30, 40 with 40 on top.

fill_row

Push node 50 onto stack

Current node (value 50) is pushed onto the stack. Current moves to null, ending traversal.

💡 Pushing the last node completes the stack with all nodes in order.

Line:

stack.append(current)
current = current.next

💡 Stack now contains all nodes: 10, 20, 30, 40, 50 with 50 on top.

compare

Check if n is greater than stack size

We compare n (2) with the stack size (5). Since 2 ≤ 5, we proceed to pop nodes.

💡 This check prevents errors if n is larger than the list length.

Line:

if n > len(stack):
    return None

💡 The stack has enough nodes to find the nth from the end.

delete

Pop node 50 (1st pop)

Pop the top node (value 50) from the stack. This is the first pop out of n-1 (1) pops.

💡 Popping nodes moves backward from the end of the list.

Line:

for _ in range(n - 1):
    stack.pop()

💡 After this pop, the stack top is node 40, which is the nth node from the end.

delete

Pop node 40 (final pop)

Pop the next node (value 40) from the stack. This is the final pop which returns the nth node from the end.

💡 The last popped node is the answer to the problem.

Line:

return stack.pop().val

💡 Node 40 is the 2nd node from the end, so its value is returned.

reconstruct

Return the value 40

The algorithm returns the value 40, which is the 2nd node from the end of the list.

💡 Returning the value completes the algorithm and solves the problem.

Line:

return stack.pop().val

💡 The final answer is the value of the node popped last from the stack.

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

def nth_from_end(head, n):
    stack = []  # STEP 1: Initialize empty stack
    current = head  # STEP 1: Set current to head
    while current:  # STEP 2-6: Traverse list
        stack.append(current)  # STEP 2-6: Push current node
        current = current.next  # STEP 2-6: Move current forward
    if n > len(stack):  # STEP 7: Check if n is valid
        return None
    for _ in range(n - 1):  # STEP 8: Pop n-1 nodes
        stack.pop()
    return stack.pop().val  # STEP 9-10: Pop nth node and return value

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

📊

Nth Node from End of List (Return Value) - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation helps you understand how reversing traversal with a stack works to find the nth node from the end.

advance

10

→

20

→

30

→

40

→

50

connect

10

→

20

→

30

→

40

→

50

connect

10

→

20

→

30

→

40

→

50

connect

10

→

20

→

30

→

40

→

50

connect

10

→

20

→

30

→

40

→

50

advance

10

→

20

→

30

→

40

→

50

compare

10

→

20

→

30

→

40

→

50

detach

10

→

20

→

30

→

40

→

50

detach

10

→

20

→

30

→

40

→

50

Result: 40

reconstruct

10

→

20

→

30

→

40

→

50

Result: 40

Key Takeaways

✓ Using a stack reverses the traversal order, allowing easy access to nodes from the end.

This insight is hard to see from code alone because the stack abstracts the reversal, but visualization shows nodes being collected and popped in reverse.

✓ Popping n nodes from the stack corresponds to moving backward n steps from the list's end.

Visualizing each pop clarifies how the algorithm counts backward without modifying the list.

✓ The check for n > stack size prevents errors when n is larger than the list length.

Seeing this decision step helps understand the importance of input validation in linked list problems.

Practice

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

2. You are given a singly linked list and need to find the node that is exactly in the middle of the list. Which approach guarantees finding the middle node in a single pass with constant extra space?

easy

A. Store all nodes in an array, then access the middle index directly.

B. Traverse the list twice: first to count nodes, second to reach the middle node.

C. Use two pointers: move one pointer twice as fast as the other; when the fast pointer reaches the end, the slow pointer is at the middle.

D. Use a recursive approach to reach the end and count backwards to the middle.

Solution

1. Step 1: Understand the problem constraints

   The goal is to find the middle node in a single pass and O(1) space.

2. Step 2: Identify the approach that uses two pointers

   Using a slow pointer moving one step and a fast pointer moving two steps ensures when fast reaches the end, slow is at the middle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer technique is classic for single-pass middle node [OK]

Hint: Two pointers with different speeds find middle in one pass [OK]

Common Mistakes:

• Thinking counting then traversing is single pass
• Using extra space unnecessarily
• Recursion adds overhead and is not optimal

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. 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. Consider the following buggy code for finding the middle node of a linked list. Which line contains the subtle bug that can cause a runtime error?

medium

A. Line 4: while fast.next and fast.next.next:

B. Line 3: fast = head

C. Line 2: slow = head

D. Line 6: return slow

Solution

1. Step 1: Analyze loop condition

   The condition checks fast.next and fast.next.next but does not check if fast itself is null, which can cause AttributeError if fast is null.

2. Step 2: Identify fix

   Change condition to while fast and fast.next to safely access fast.next.next.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing fast null check causes runtime error on short lists [OK]

Hint: Always check fast pointer is not null before accessing next [OK]

Common Mistakes:

• Assuming fast.next is safe without checking fast
• Returning first middle node incorrectly
• Modifying list nodes accidentally