How to Solve: Remove Nth Node From End of List

How to Solve: Remove Nth Node From End of List

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 Linked List interviews—master it, and you prove you can handle edge cases, two-pointer techniques, and in-place modifications under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before attempting this problem, ensure you understand: 1. Singly Linked List Traversal – How to iterate, insert, and delete nodes. 2. Two-Pointer Technique – Fast and slow pointers (e.g., cycle detection, middle of list). 3. Dummy Node Pattern – Simplifies edge cases (e.g., deleting the head node).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every "Remove Nth from End" problem.)

1. Edge Case Check
2. If head is None or n == 0, return head.

3. If n == length of list, delete the head (special case).

4. Initialize Dummy Node

5. dummy = ListNode(0)
6. dummy.next = head

7. This ensures we can handle head deletion uniformly.

8. Two-Pointer Setup

9. fast = dummy

10. slow = dummy

11. Move Fast Pointer Ahead by N+1 Steps

12. for _ in range(n + 1): fast = fast.next

13. This creates a gap of N nodes between fast and slow.

14. Move Both Pointers Until Fast Reaches End

15. while fast: slow = slow.next; fast = fast.next

16. Now, slow is at the node before the one to delete.

17. Delete the Target Node

18. slow.next = slow.next.next

19. Return the Modified List

20. return dummy.next

? WORKED EXAMPLES

Example 1 – Basic (Remove 2nd from End)

Problem: Given 1 → 2 → 3 → 4 → 5, remove the 2nd node from the end (4).

Step-by-Step Execution: 1. Edge Case Check: head is not None, n = 2 (valid). 2. Dummy Node:
python
dummy = ListNode(0)
dummy.next = head # dummy → 1 → 2 → 3 → 4 → 5 3. Two-Pointer Setup:
python
fast = dummy
slow = dummy 4. Move Fast Ahead by N+1 (3 steps):
python
fast = fast.next # 1
fast = fast.next # 2
fast = fast.next # 3
Now: fast at 3, slow at dummy. 5. Move Both Until Fast Reaches End:
python
while fast:
slow = slow.next # 1 → 2 → 3
fast = fast.next # 4 → 5 → None
Now: slow at 3, fast at None. 6. Delete Node:
python
slow.next = slow.next.next # 3 → 5 (skips 4) 7. Return Result:
python
return dummy.next # 1 → 2 → 3 → 5

Full Code (Python):

class ListNode:

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

        self.val = val

        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:

    dummy = ListNode(0)

    dummy.next = head

    fast = slow = dummy


    # Move fast N+1 steps ahead

    for _ in range(n + 1):

        fast = fast.next


    # Move both until fast reaches end

    while fast:

        slow = slow.next

        fast = fast.next


    # Delete the target node

    slow.next = slow.next.next


    return dummy.next

Time Complexity: O(L) (one pass) Space Complexity: O(1) (constant extra space)

Why This Works: - The N+1 gap ensures slow stops before the target node. - The dummy node handles head deletion uniformly.

Example 2 – Medium (Remove Head Node)

Problem: Given 1 → 2, remove the 2nd node from the end (1).

Step-by-Step Execution: 1. Edge Case Check: n = 2, list length = 2 → delete head. 2. Dummy Node:
python
dummy = ListNode(0)
dummy.next = head # dummy → 1 → 2 3. Two-Pointer Setup:
python
fast = slow = dummy 4. Move Fast Ahead by N+1 (3 steps):
python
fast = fast.next # 1
fast = fast.next # 2
fast = fast.next # None 5. Move Both Until Fast Reaches End:
- fast is already None, so loop doesn’t run. 6. Delete Node:
python
slow.next = slow.next.next # dummy → 2 7. Return Result:
python
return dummy.next # 2

Full Code: (Same as Example 1—dummy node handles this automatically!)

Why This Works: - The N+1 gap ensures slow stops at dummy when deleting the head. - No special case needed.

Example 3 – Hard/Follow-Up (One-Pass with Constraints)

Problem: "Can you solve this in one pass without knowing the length of the list?" (This is the standard follow-up in FAANG interviews.)

Solution: (Already covered in Example 1! The two-pointer approach is inherently one-pass.)

Follow-Up Twist: "What if the list is circular?" Approach: 1. Detect cycle using Floyd’s Tortoise and Hare. 2. If cycle exists, compute length L and adjust n to n % L. 3. Proceed with the two-pointer method.

Full Code (Circular List Handling):

def removeNthFromEndCircular(head: ListNode, n: int) -> ListNode:

    # Step 1: Detect cycle and find length

    slow = fast = head

    has_cycle = False

    while fast and fast.next:

        slow = slow.next

        fast = fast.next.next

        if slow == fast:

            has_cycle = True

            break


    if has_cycle:

        # Compute cycle length

        cycle_length = 1

        fast = fast.next

        while slow != fast:

            fast = fast.next

            cycle_length += 1

        # Adjust n

        n = n % cycle_length


    # Step 2: Standard two-pointer removal

    dummy = ListNode(0)

    dummy.next = head

    fast = slow = dummy

    for _ in range(n + 1):

        fast = fast.next

    while fast:

        slow = slow.next

        fast = fast.next

    slow.next = slow.next.next

    return dummy.next

Why This Works: - Cycle detection ensures correctness in circular lists. - Modulo operation adjusts n to the effective position.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Here’s the 30-second cheat sheet for ‘Remove Nth from End’:

1. Dummy Node First – Always start with dummy = ListNode(0); dummy.next = head. This handles head deletion automatically.
2. Two-Pointer Gap – Move fast ahead by N+1 steps. This ensures slow stops before the target node.
3. One Pass Only – Move both pointers until fast hits None. Delete slow.next.
4. Edge Cases – Check for empty list, n = 0, or n = list length. The dummy node covers most of these.

If they ask for a follow-up, remember: the two-pointer method is already one-pass. For circular lists, detect the cycle first, then adjust n with modulo.

Now go crush that interview. You’ve got this!

? FINAL NOTES

• Practice Variations:
• Remove every Nth node from the end (e.g., every 2nd node).
• Remove Nth node from the end in a doubly linked list.
• Time/Space Complexity: Always O(L) time, O(1) space.
• Whiteboard Tip: Draw the list and pointers at each step to visualize the gap.

This framework is directly usable in any FAANG interview. Memorize the steps, practice the edge cases, and you’ll solve this problem flawlessly. ?