Remove Nth Node From End Of The Linked List

Problem Statement

Given a singly linked list along with a positive integer N. Write a function to delete the Nth node from the end of the given linked list.

Problem Statement Understanding

Let's understand the given problem with the help of some examples:

If our initial linked list:

It means that here we had to remove the N = 3rd node from the end which is 3, so we will remove it.

After removing the 3rd node from the end of the linked list, our output resultant linked list is

If our initial linked list:

It means that here we had to remove the N=1st node from the end which is 6, so we will remove it.

After removing the 1st node from the end of the linked list, our output resultant linked list is:

I hope that now you have understood this problem. Now, think of how we can approach this problem?

One simple approach will be to first find the length of linked list and then using it find the Nth node from the end. Let’s see how we will do this.

If length of our linked list is P, it means that we have to find (P-N)th node from the beginning of the linked list and this node will be the Nth node from the end of the linked list.

So to delete Nth node using the above approach we will have to first traverse the linked list and find the length P of the linked list. Then we will have to again traverse the linked list (P-N+1) steps to reach the Nth node from the end.

This will work fine, but it is taking 2 traversals of linked list to find the Nth node from the end. Now try to think, do we actually require the length of linked list to find the Nth node from the end of the linked list?

So in approach we will see how we can do it in single traversal of linked list.

Approach

Our approach would be simple.
To remove the Nth node from the end, we need two things, which are:
1) the Nth node from the end and
2) the node just before it.

First, we need to find the Nth node from the end of the linked list. There are many ways to do so. We will use the most efficient one, i.e., using 2 pointers.

We start with 2 pointers from the head.

  • Move one of them to the Nth node.
  • Now, both pointers are N nodes apart. If we move them forward together, that distance will be maintained.
  • Now, move both the pointers together till the forward pointer points to the last node.
  • Now, the backward pointer is N nodes far from the forward node. So, it will point to the nth node from the end. That is our required node to delete, so we delete it.

Think of some cases that we have to take care of while performing this operation, also try to implement the approach yourself.

Below is the step-by-step algorithm for the above approach.

Algorithm

  • Initialize 2 pointers i and j pointing to head node.
  • Move the pointer j, N steps ahead.
  • If we reach the end before reaching the Nth node, this means N is greater than the length of the linked list (Nth node doesn’t exist). So, we simply stop and return.
  • Else declare a prev pointer to keep track of the node just before the node pointed by i.
  • Now move both the pointers, i and j, together(along with the prev pointe) till j reaches the end node.
  • Now, i will be pointing to the Nth node from the end.
  • Now we have to remove it from the linked list.
  • First, we simply disconnect the ith node from the linked list by doing prev->next = i->next.
  • If the node to remove is the first node, we need to modify the head pointer as well.
  • At the end, delete i.

Dry Run

Code Implementation:

#include 
#include 

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;
}


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

    insert_at_begenning(&head,80);
    insert_at_begenning(&head,70);
    insert_at_begenning(&head,60);
    insert_at_begenning(&head,50);
    insert_at_begenning(&head,40);
    insert_at_begenning(&head,30);
    insert_at_begenning(&head,20);
    insert_at_begenning(&head,10);

    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;
}
#include
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

void remove_nth_node_from_end(Node** head, int n){
    Node *i, *j;
    i = j = *head;

    n--;
    // move j n steps ahead
    while(n>0 && j->next!=NULL){
        j = j->next;
        n--;
    }

    if(n!=0){
        cout<<"n is either <= 0 or larger than the linked list size\n";
        return;
    }

    // move i and j together till j reaches the end
    Node *prev = i;
    while(j->next!=NULL){
        prev = i;
        i = i->next;
        j = j->next;
    }

    // now i will point to the nth node from end
    // remove it
    prev->next = i->next;

    // if i points to first node
    // modify the head pointer as well
    if(i == *head){
        *head = i->next;
    }
    delete i;
}


int main(){
    Node* head = NULL;

    push_front(&head, 5);
    push_front(&head, 4);
    push_front(&head, 3);
    push_front(&head, 2);
    push_front(&head, 1);

    printList(head);
    // 1 2 3 4 5
    
    // to remove 3rd node from end
    remove_nth_node_from_end(&head, 3);

    printList(head);
    // 1 2 4 5
}

class RemoveEnd 
{
	Node head;
	class Node 
    {
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	// Function to delete the nth node from
	// the end of the given linked list
	void deleteNode(int key)
	{

		// First pointer will point to
		// the head of the linked list
		Node first = head;

		// Second pointer will point to the
		// Nth node from the beginning
		Node second = head;
		for (int i = 0; i < key; i++) {

			// If count of nodes in the given
			// linked list is <= N
			if (second.next == null) {

				// If count = N i.e. delete the head node
				if (i == key - 1)
					head = head.next;
				return;
			}
			second = second.next;
		}
		// Increment both the pointers by one until
		// second pointer reaches the end
		while (second.next != null) {
			first = first.next;
			second = second.next;
		}
		// First must be pointing to the
		// Nth node from the end by now
		// So, delete the node first is pointing to
		first.next = first.next.next;
	}
	public void push(int new_data)
	{
		Node new_node = new Node(new_data);
		new_node.next = head;
		head = new_node;
	}
	public void printList()
	{
		Node tnode = head;
		while (tnode != null) {
			System.out.print(tnode.data + " ");
			tnode = tnode.next;
		}
	}
	public static void main(String[] args)
	{
		RemoveEnd llist = new RemoveEnd();

		llist.push(7);
		llist.push(1);
		llist.push(3);
		llist.push(2);

		System.out.println("\nCreated Linked list is:");
		llist.printList();

		int N = 1;
		llist.deleteNode(N);

		System.out.println("\nLinked List after Deletion is:");
		llist.printList();
	}
}

class Node:

	def __init__(self, data):
		self.data = data 
		self.next = None 

class LinkedList:

	def __init__(self):
		self.head = None

	def create(self, x):

		new_node = Node(x)

		if self.head is None:
			self.head = new_node
			return

		last = self.head
		while last.next:
			last = last.next

		last.next = new_node

	def display(self):
		temp = self.head

		while temp:
			print(temp.data, end = " ")
			temp = temp.next

def removeNthFromEnd(head, k):
	
	first = head
	second = head
	count = 1
	while count <= k:
		second = second.next
		count += 1
	if second is None:
		head.value = head.next.value
		head.next = head.next.next
		return
	while second.next is not None:
		first = first.next
		second = second.next
	first.next = first.next.next


val = [1, 2, 3, 4, 5]
k = 3
ll = LinkedList()
for i in val:
	ll.create(i)

print("Linked list before modification:");
ll.display()

removeNthFromEnd(ll.head, k)

print("\nLinked list after modification:");
ll.display()

Output

1 2 3 4 5
1 2 4 5

[forminator_quiz id="3861"]

Space complexity: O(1), as we are not using any extra space here.

Here N is the total number of nodes in the given linked list.

Through this article, we learned how to remove the nth node from the end of a linked list. Problems like these are good for strengthening your concepts in LinkedList. I would highly recommend you to practice more such problems from Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *