Remove Nth Node from End of List in DSA Java - Execution Trace

Concept Flow - Remove Nth Node from End of List

Start with head node

↓

Set two pointers: fast and slow at head

↓

Move fast pointer n steps ahead

↓

Move both fast and slow pointers one step until fast.next reaches end

↓

Slow pointer now at node before target

↓

Change slow.next to skip target node

↓

Return head of modified list

We use two pointers to find the node before the one to remove, then skip it.

Execution Sample

DSA Java

ListNode removeNthFromEnd(ListNode head, int n) {
  ListNode fast = head, slow = head;
  for (int i = 0; i < n; i++) fast = fast.next;
  if (fast == null) return head.next;
  while (fast.next != null) {
    fast = fast.next; slow = slow.next;
  }
  slow.next = slow.next.next;
  return head;
}

Removes the nth node from the end of a singly linked list using two pointers.

Execution Table

Step	Operation	Fast Pointer	Slow Pointer	List State	Pointer Changes
1	Initialize fast and slow at head	1	1	1 -> 2 -> 3 -> 4 -> 5 -> null	fast=head(1), slow=head(1)
2	Move fast 1 step ahead (i=0)	2	1	1 -> 2 -> 3 -> 4 -> 5 -> null	fast=2
3	Move fast 2 steps ahead (i=1)	3	1	1 -> 2 -> 3 -> 4 -> 5 -> null	fast=3
4	Fast moved n=2 steps ahead	3	1	1 -> 2 -> 3 -> 4 -> 5 -> null	fast at 3, slow at 1
5	Move both pointers until fast.next is null	4	2	1 -> 2 -> 3 -> 4 -> 5 -> null	fast=4, slow=2
6	Move both pointers	5	3	1 -> 2 -> 3 -> 4 -> 5 -> null	fast=5, slow=3
7	fast.next is null, stop moving	5	3	1 -> 2 -> 3 -> 4 -> 5 -> null	stop
8	Remove node after slow (node 4)	5	3	1 -> 2 -> 3 -> 5 -> null	slow.next = slow.next.next
9	Return modified list head	5	3	1 -> 2 -> 3 -> 5 -> null	return head

💡 fast.next is null at step 7, slow is before node to remove

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	Final
fast	1	2	3	4	5	5	5
slow	1	1	1	2	3	3	3
List	1->2->3->4->5->null	1->2->3->4->5->null	1->2->3->4->5->null	1->2->3->4->5->null	1->2->3->4->5->null	1->2->3->5->null	1->2->3->5->null

Key Moments - 3 Insights

Why do we move the fast pointer n steps ahead before moving slow?

Moving fast n steps ahead creates a gap so when fast reaches the end, slow is right before the node to remove (see steps 2-4 in execution_table).

What if fast becomes null after moving n steps?

If fast is null after moving n steps (step 4), it means we must remove the head node, so we return head.next directly.

Why do we stop moving when fast.next is null, not fast?

Stopping at fast.next null means slow is just before the target node, allowing us to change slow.next to skip the target (step 7).

Visual Quiz - 3 Questions

Look at the execution_table, what is the position of the slow pointer at step 6?

A Node with value 3

B Node with value 2

C Node with value 4

D Node with value 5

💡 Hint

Check the 'Slow Pointer' column at step 6 in execution_table.

At which step does the list change by removing a node?

A Step 7

B Step 5

C Step 8

D Step 9

💡 Hint

Look for 'Remove node' operation and list state change in execution_table.

If n was 5 (length of list), what would happen after moving fast pointer n steps?

A fast would point to last node

B fast would be null and head node removed

C slow would move forward immediately

D Nothing changes

💡 Hint

Refer to key_moments about fast pointer becoming null after n steps.

Concept Snapshot

Remove Nth Node from End of List:
- Use two pointers: fast and slow at head
- Move fast n steps ahead
- If fast is null, remove head
- Move both until fast.next is null
- slow.next = slow.next.next to remove node
- Return head of modified list

Full Transcript

This concept removes the nth node from the end of a singly linked list. We start with two pointers at the head. First, move the fast pointer n steps ahead. If fast becomes null, it means the head node is the one to remove, so return head.next. Otherwise, move both fast and slow pointers one step at a time until fast.next is null. At this point, slow is just before the node to remove. Change slow.next to skip the target node. Finally, return the head of the updated list. This method ensures we find the correct node to remove in one pass.

Practice

1. What does the problem "Remove Nth Node from End of List" ask you to do with a linked list?

easy

A. Reverse the entire linked list

B. Add a new node at the Nth position from the start

C. Find the value of the Nth node from the start

D. Remove the node that is Nth from the end of the list

Solution

1. Step 1: Understand the problem statement

   The problem requires removing the node that is Nth from the end of the linked list, not from the start.

2. Step 2: Clarify the operation on the list

   We do not add or reverse nodes; we specifically remove one node counting from the end.

3. Final Answer:

   Remove the node that is Nth from the end of the list -> Option D

4. Quick Check:

   Remove Nth from end = Remove Nth from end [OK]

Hint: Focus on 'Nth from end' means counting backwards [OK]

Common Mistakes:

• Confusing Nth from end with Nth from start
• Thinking the problem asks to add or reverse nodes
• Ignoring the direction of counting nodes

2. Which of the following Java method signatures correctly represents a function to remove the Nth node from the end of a singly linked list?

easy

A. public ListNode removeNthFromEnd(ListNode head, int n)

B. public void removeNthFromEnd(int n, ListNode head)

C. public ListNode removeNode(ListNode head, int index)

D. public ListNode deleteNthNode(ListNode node, int n)

Solution

1. Step 1: Check method parameters and return type

   The method should take the head of the list and an integer n, and return the new head after removal.

2. Step 2: Match signature with problem requirements

   public ListNode removeNthFromEnd(ListNode head, int n) matches the expected signature: it takes (ListNode head, int n) and returns ListNode.

3. Final Answer:

   public ListNode removeNthFromEnd(ListNode head, int n) -> Option A

4. Quick Check:

   Correct signature = public ListNode removeNthFromEnd(ListNode head, int n) [OK]

Hint: Method must return updated head and accept head, n as parameters [OK]

Common Mistakes:

• Wrong parameter order
• Void return type instead of ListNode
• Using incorrect parameter types

3. What will be the output linked list after removing the 2nd node from the end in the list: 1 -> 2 -> 3 -> 4 -> 5 -> null?

medium

A. 1 -> 2 -> 4 -> 5 -> null

B. 1 -> 2 -> 3 -> 5 -> null

C. 1 -> 3 -> 4 -> 5 -> null

D. 2 -> 3 -> 4 -> 5 -> null

Solution

1. Step 1: Identify the 2nd node from the end

   Counting from the end: 5 (1st), 4 (2nd). So node with value 4 is to be removed.

2. Step 2: Remove node with value 4 and link previous node to next

   After removal, list becomes 1 -> 2 -> 3 -> 5 -> null.

3. Final Answer:

   1 -> 2 -> 3 -> 5 -> null -> Option B

4. Quick Check:

   Remove 2nd from end = Remove node 4 [OK]

Hint: Count nodes from end to find which to remove [OK]

Common Mistakes:

• Removing wrong node counting from start
• Off-by-one errors in counting
• Not updating links correctly after removal

4. Given the following code snippet to remove the Nth node from the end, what is the error?

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head;
    ListNode slow = head;
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
}

medium

A. The for loop should run from i = 0 to i < n, not i <= n

B. The slow pointer should start at null, not head

C. The method should return slow, not head

D. The while loop condition should be fast.next != null

Solution

1. Step 1: Analyze the for loop for moving fast pointer

   The loop runs i from 0 to n inclusive (i <= n), moving fast n+1 steps, which is one step too many and causes NullPointerException.

2. Step 2: Correct the loop to run i < n to move fast exactly n steps ahead

   This ensures fast is n nodes ahead of slow, allowing correct removal of the target node.

3. Final Answer:

   The for loop should run from i = 0 to i < n, not i <= n -> Option A

4. Quick Check:

   Loop count off by one = The for loop should run from i = 0 to i < n, not i <= n [OK]

Hint: Check loop bounds carefully for pointer steps [OK]

Common Mistakes:

• Using i <= n instead of i < n in loop
• Starting slow pointer incorrectly
• Returning wrong node after removal

5. You have a linked list: 10 -> 20 -> 30 -> 40 -> 50 -> null. You want to remove the 5th node from the end. What will be the resulting list after removal?

hard

A. 30 -> 40 -> 50 -> null

B. 10 -> 20 -> 30 -> 40 -> null

C. 20 -> 30 -> 40 -> 50 -> null

D. 10 -> 20 -> 30 -> 40 -> 50 -> null

Solution

1. Step 1: Identify the 5th node from the end

   Since the list has 5 nodes, the 5th from the end is the first node with value 10.

2. Step 2: Remove the first node and update head

   Removing node 10 means the new head is node 20, so list becomes 20 -> 30 -> 40 -> 50 -> null.

3. Final Answer:

   20 -> 30 -> 40 -> 50 -> null -> Option C

4. Quick Check:

   Remove first node = 20 -> 30 -> 40 -> 50 -> null [OK]

Hint: If N equals list length, remove head node [OK]

Common Mistakes:

• Not updating head when first node is removed
• Removing wrong node counting from end
• Confusing list length with N