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 problem where you repeatedly transform a number by replacing it with the sum of the squares of its digits. The goal is to determine if this process eventually reaches 1 or falls into a repeating cycle. Which algorithmic approach is best suited to efficiently detect cycles in this implicit sequence without extra space?

easy

A. Dynamic Programming with memoization to store intermediate results

B. Breadth-First Search (BFS) to explore all possible transformations

C. Greedy approach to pick the next number with the smallest digit sum

D. Floyd's Cycle Detection (Fast and Slow Pointers) to detect cycles in sequences

Solution

1. Step 1: Understand the problem as detecting cycles in a sequence generated by a function

   The problem involves repeatedly applying a function to a number to generate a sequence. Detecting if this sequence reaches 1 or cycles indefinitely is a classic cycle detection problem.

2. Step 2: Identify Floyd's Cycle Detection as the optimal approach

   Floyd's fast and slow pointers efficiently detect cycles in sequences without extra space, unlike DP or BFS which require additional memory or are not suited for implicit sequences.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection in implicit sequences -> Floyd's algorithm [OK]

Hint: Cycle detection in sequences -> Floyd's fast-slow pointers [OK]

Common Mistakes:

• Confusing cycle detection with DP or BFS approaches

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. Given the following code for finding the middle node of a linked list, what is the value returned when the input list is 1 -> 2 -> 3 -> 4?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace slow and fast pointers

   Initial: slow=1, fast=1; Iteration 1: slow=2, fast=3; Iteration 2: fast.next is null, loop ends.

2. Step 2: Return slow's value

   Slow points to node with value 3 at loop end.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   For even length, returns second middle node (3) [OK]

Hint: Fast pointer moves twice as fast; slow ends at middle [OK]

Common Mistakes:

• Returning first middle node for even length
• Off-by-one errors in loop condition
• Confusing slow and fast pointer positions

4. What is the time complexity of Floyd's Tortoise and Hare algorithm for finding the duplicate number in an array of size n+1 with values from 1 to n?

medium

A. O(n) because each pointer moves at most n steps before meeting

B. O(n^2) due to nested pointer updates

C. O(n log n) due to implicit sorting in pointer jumps

D. O(n) but with O(n) extra space for visited nodes

Solution

1. Step 1: Analyze pointer movements

   Slow pointer moves one step at a time, fast pointer moves two steps. They meet within O(n) steps because the cycle length is at most n.

2. Step 2: Confirm no nested loops or extra space

   There are no nested loops; each iteration advances pointers. Space is O(1), so no extra overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time complexity matches pointer traversal count [OK]

Hint: Two pointers meet in linear time, no nested loops [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing pointer jumps with sorting complexity
• Thinking extra space is used for visited nodes

5. What is the time and space complexity of Floyd's cycle detection algorithm used to find the start of a cycle in a linked list of length n?

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(n log n), Space: O(1)

Solution

1. Step 1: Analyze time complexity of pointer movements

   Fast pointer moves twice as fast as slow pointer, so they meet in O(n) steps, and locating cycle start also takes O(n) steps, total O(n).

2. Step 2: Analyze space complexity

   Only a fixed number of pointers are used, no extra data structures, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space are standard for Floyd's algorithm [OK]

Hint: Two pointers traverse list linearly, no extra space needed [OK]

Common Mistakes:

• Confusing space with hash set approach
• Assuming quadratic time due to nested loops
• Mistaking recursion stack space