Remove Nth Node from End of List in DSA C

Mental Model

To remove the nth node from the end, we find the node just before it by moving two pointers with a fixed gap.

Analogy: Imagine two friends walking on a path where one starts n steps ahead. When the front friend reaches the end, the other is right before the target spot to remove.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑         ↑
        slow      fast

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, remove 2nd node from end

Goal: Remove the 2nd node from the end, which is node with value 4

Step 1: Move fast pointer 2 steps ahead

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          slow ↑         fast ↑

Why: Create a gap of n=2 between slow and fast pointers

Step 2: Move both slow and fast pointers one step until fast reaches the end

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
               slow ↑               fast ↑

Why: Keep the gap so slow points to node before target

Step 3: Move both pointers one more step

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                    slow ↑                    fast ↑

Why: Slow is now just before the node to remove

Step 4: Remove node after slow by linking slow to slow->next->next

head -> 1 -> 2 -> 3 -> 5 -> null

Why: Skip the 4th node to remove it

Result:

head -> 1 -> 2 -> 3 -> 5 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// Helper to create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

// Function to remove nth node from end
Node* removeNthFromEnd(Node* head, int n) {
    Node dummy;
    dummy.next = head;
    Node* slow = &dummy;
    Node* fast = &dummy;

    // Move fast n steps ahead
    for (int i = 0; i < n; i++) {
        fast = fast->next; // advance fast pointer
    }

    // Move both pointers until fast reaches the last node
    while (fast->next != NULL) {
        slow = slow->next; // advance slow pointer
        fast = fast->next; // advance fast pointer
    }

    // Remove the nth node from end
    Node* toDelete = slow->next;
    slow->next = slow->next->next; // bypass the node
    free(toDelete); // free memory

    return dummy.next;
}

// Helper to print list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d", curr->val);
        if (curr->next != NULL) printf(" -> ");
        curr = curr->next;
    }
    printf(" -> null\n");
}

int main() {
    // Create list 1->2->3->4->5
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    printf("Original list: ");
    printList(head);

    int n = 2;
    head = removeNthFromEnd(head, n);

    printf("After removing %dth node from end: ", n);
    printList(head);

    return 0;
}

for (int i = 0; i < n; i++) { fast = fast->next; // advance fast pointer }

advance fast pointer n steps to create gap

while (fast->next != NULL) { slow = slow->next; // advance slow pointer fast = fast->next; // advance fast pointer }

move both pointers until fast reaches end

slow->next = slow->next->next; // bypass the node

remove nth node by skipping it

Output

Original list: 1 -> 2 -> 3 -> 4 -> 5 -> null

After removing 2th node from end: 1 -> 2 -> 3 -> 5 -> null

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because we use only a few pointers, no extra list

vs Alternative: Compared to counting length first then removing, this uses one pass instead of two, saving time

Edge Cases

Removing the head node (n equals list length)

Dummy node helps remove head easily without special code

DSA C

Node dummy; dummy.next = head;

List with only one node and n=1

Returns empty list (null) after removal

DSA C

slow->next = slow->next->next;

n is 1 (remove last node)

Slow pointer stops at second last node and removes last node

DSA C

while (fast->next != NULL)

When to Use This Pattern

When asked to remove a node from the end of a linked list in one pass, use two pointers spaced n apart to find the target efficiently.

Common Mistakes

Mistake: Not using a dummy node and failing when removing the head node
Fix: Use a dummy node pointing to head to simplify edge cases

Mistake: Moving fast pointer n+1 steps instead of n, causing null pointer errors
Fix: Move fast pointer exactly n steps ahead before moving both pointers

Mistake: Not freeing the removed node's memory
Fix: Call free() on the removed node to avoid memory leaks

Summary

Removes the nth node from the end of a singly linked list in one pass.

Use when you need efficient removal from the end without counting list length first.

Keep two pointers n nodes apart so when the front reaches the end, the back is just before the target.

Practice

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

easy

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

B. Remove the node that is Nth from the start of the list

C. Add a new node at the Nth position from the end

D. Reverse the linked list up to the Nth node from the end

Solution

1. Step 1: Understand the problem statement

   The problem requires removing the node that is exactly N positions from the end of the linked list.

2. Step 2: Clarify the difference from other options

   Options A, C, and D describe different operations: removing from start, adding nodes, or reversing, which are not asked here.

3. Final Answer:

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

4. Quick Check:

   Remove Nth from end = Remove the node that is Nth from the end of the list [OK]

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

Common Mistakes:

• Confusing Nth from start with Nth from end
• Thinking the problem asks to add nodes
• Assuming the list needs reversing

2. Which of the following is the correct way to declare a pointer to the head of a singly linked list in C?

easy

A. struct Node head*;

B. Node head*;

C. struct Node* head;

D. Node* head;

Solution

1. Step 1: Recall C struct pointer syntax

   In C, to declare a pointer to a struct Node, use 'struct Node* head;'.

2. Step 2: Identify incorrect syntax

   Options A, B, and D misuse the order or omit 'struct' keyword which is required unless typedef is used.

3. Final Answer:

   struct Node* head; -> Option C

4. Quick Check:

   Pointer to struct Node = struct Node* head; [OK]

Hint: Remember 'struct' keyword before struct name in C [OK]

Common Mistakes:

• Omitting 'struct' keyword in declaration
• Placing '*' incorrectly after variable name
• Using typedef name without defining it

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. 2 -> 3 -> 4 -> 5 -> null

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

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

Solution

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

   The list is 1->2->3->4->5. Counting from 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 to next

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

3. Final Answer:

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

4. Quick Check:

   Remove 2nd from end (4) = 1->2->3->5->null [OK]

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

Common Mistakes:

• Removing the wrong node counting from start
• Skipping the link update after removal
• Confusing 2nd from end with 2nd from start

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

struct Node* removeNthFromEnd(struct Node* head, int n) {
    struct Node* fast = head;
    struct Node* slow = head;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return head;
}

medium

A. The slow pointer is moved too many times causing segmentation fault

B. The loop does not check if fast becomes NULL before accessing fast->next

C. The function does not handle the case when n is zero

D. The function returns the wrong pointer instead of head

Solution

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

   The loop moves fast pointer n times without checking if fast is NULL, which can cause a crash if n is larger than list length.

2. Step 2: Check while loop condition and pointer usage

   The while loop uses fast->next without null check before the loop, which is unsafe if fast is NULL.

3. Final Answer:

   The loop does not check if fast becomes NULL before accessing fast->next -> Option B

4. Quick Check:

   Missing NULL check on fast pointer causes error [OK]

Hint: Always check pointers for NULL before dereferencing [OK]

Common Mistakes:

• Not checking if fast is NULL before fast->next
• Assuming list length is always >= n
• Ignoring edge case when removing head node

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?

hard

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

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

C. 10 -> 20 -> 30 -> 40 -> 50 -> null (no change)

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

Solution

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

   The list length is 5, so the 5th node from the end is the first node with value 10.

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

   Removing the first node results in the list: 20 -> 30 -> 40 -> 50 -> null.

3. Final Answer:

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

4. Quick Check:

   Remove 5th from end (head) = list without first node [OK]

Hint: Removing N equals list length means remove head [OK]

Common Mistakes:

• Not updating head pointer when removing first node
• Confusing Nth from end with Nth from start
• Assuming no change if N equals list length