Remove Nth Node From End of List - C Solution

1. Introduction

In this post, we will address a common problem in linked list manipulation - "Remove Nth Node From End of List". This problem involves removing a specific node from a linked list, not by its position from the start, but from the end. It's an excellent exercise in understanding two-pointer techniques and linked list traversal in C.

Problem

Given the head of a linked list, the task is to remove the nth node from the end of the list and return the head of the modified list.

2. Solution Steps

1. Use two pointers: a fast pointer and a slow pointer.

2. Move the fast pointer n steps ahead.

3. Move both pointers until the fast pointer reaches the end of the list.

4. This places the slow pointer just before the node to be removed.

5. Adjust the pointers to remove the nth node.

6. Handle edge cases, like removing the first node.

3. Code Program

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

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

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

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

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

    struct ListNode* temp = slow->next;
    slow->next = slow->next->next;
    free(temp);

    return dummy.next;
}

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

// Main function to test the removeNthFromEnd function
int main() {
    // Create and initialize a linked list for demonstration
    struct ListNode* 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);

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

    // Print and free the modified linked list
    struct ListNode* temp;
    while (head != NULL) {
        printf("%d ", head->val);
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Output:

1 2 3 5

Explanation:

1. The removeNthFromEnd function uses a two-pointer approach to locate the nth node from the end.

2. The fast pointer is moved n steps ahead, and then both pointers move together until the fast pointer reaches the end.

3. The slow pointer is now at the correct position to remove the nth node.

4. The main function demonstrates this with an example list and prints the result after removal.