Leetcode
Random

Click random to get a fresh chapter.

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

Technique / Pattern	When to Use	Quick Example
Two-Pointer (Fast & Slow)	Find the Nth node from the end in one pass.	fast moves N steps ahead, then slow starts. When fast hits end, slow is at the Nth node from end.
Dummy Node	Handle edge cases (e.g., deleting head).	dummy = ListNode(0); dummy.next = head. Now, dummy.next is always the head.
Single Pass with Offset	Optimize time complexity to O(L).	Maintain a gap of N nodes between fast and slow.

---

? 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

Mistake	Why It Happens	Correct Approach
Off-by-One Error	Moving fast by N steps instead of N+1.	Move fast by N+1 to ensure slow stops before the target node.
Not Handling Head Deletion	Forgetting to check if n == list length.	Use a dummy node to handle head deletion uniformly.
Assuming List Length is Known	Trying to compute length first (two passes).	Use the two-pointer method for one-pass efficiency.
Null Pointer Dereference	Not checking fast.next in the loop.	Always check while fast and fast.next in cycle detection.
Incorrect Gap Calculation	Using N instead of N+1 for the gap.	The gap must be N+1 to stop slow at the node before the target.

---

? INTERVIEW TrapS

Trap	How to Spot It	How to Avoid It
"What if N > list length?"	Interviewer asks about invalid n.	Clarify constraints (e.g., 1 ≤ n ≤ list length). If not given, handle gracefully.
"Can you do it in one pass?"	Follow-up question after initial solution.	Use the two-pointer method (already one-pass).
"What if the list is empty?"	Edge case not covered in examples.	Explicitly check if not head: return head at the start.

---

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