Remove Nth Node from End of List

Problem description:

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Here I shall be solving with 2 different type of solution.

Solution 1: Fast and slow pointer solution
Solution 2: Two-star or pointer to pointer solution.

Solution 1: Fast and slow pointer solution

Below are the steps we shall be performing:

Step 1: Take 2 pointers [slow and fast pointer] referencing to the head pointer.
Step 2: Move the fast pointer N steps ahead.
Step 3: Till fast pointer is not equal to NULL, move both pointers 1 step at a time.
Step 4: If the next step of fast pointer is NULL, delete the node pointed by slow pointer.

Usually in the interviews, candidates will end the answer here. But the important step here is to delete the memory allocated for that deleted node. Else it will result in memory leak! So don’t forget to include it.

Visualization of above steps:

Solution in c:

/*
* File     : remove_nth_node_from_list.c
* Author   : prodevelopertutorial.com
* Purpose  : Remove Nth Node From End of List
* Copyright: @ prodevelopertutorial.com
*/

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

struct Node
{
    int data;
    struct Node* next;
};

// since we are 
void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}
struct Node * delete_node_from_end(struct Node *head, int num)
{

    // initialize both slow_pointer and fast_pointer pointing to head pointer
    struct Node *slow_pointer = head, *fast_pointer = head;

    // move fast pointer num steps ahead
    for (int i = 0; i < num; i++)
        fast_pointer = fast_pointer->next;

    // while fast_pointer is not null, increment both pointers one step at a time
    while (fast_pointer->next) 
    {
        fast_pointer = fast_pointer->next;
        slow_pointer = slow_pointer->next;
    }

    // once we get the node to be deleted, get that node, 
    //      store it in a local variable. This is because, it can be deleted later
    struct Node *node_to_be_deleted = slow_pointer->next;

    // link the slow pointer point to the next element
    slow_pointer->next = slow_pointer->next->next;
    
    // free the memory allocated for that pointer
    free(node_to_be_deleted);

    return head;
}

 struct Node * mergeTwoLists(struct Node *List_one, struct Node *List_two) 
 {
        ListNode dummy(INT_MIN);
        ListNode *tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
}

int main()
{
    struct Node *head = NULL; 

    insert_at_begenning(&head,8);
    insert_at_begenning(&head,7);
    insert_at_begenning(&head,6);
    insert_at_begenning(&head,5);
    insert_at_begenning(&head,4);
    insert_at_begenning(&head,3);
    insert_at_begenning(&head,2);
    insert_at_begenning(&head,1);

    printf("The present linked list is\n");
    display_list(&head);

    head = delete_node_from_end(head, 2);
    printf("The linked list after deleting 2nd element from end is  is\n");
    display_list(&head);

    return 0;
}