Home » Technical Interview Questions » LinkedList Interview Questions » Delete a node of a linked list at given position

Delete a node of a linked list at given position

Reading Time - 3 mins

For the given linked list write a function to delete a node at the given position.


Time complexity : O (n)


a. If list is empty, just return.

b. If position equal to 0 to be deleted, we need to delete head node.

       1. Change head reference to head->next

2. Delete the old head. (free(head))

c.  Create a temp node(auxiliary node to store reference of node to be deleted).

d. Find previous node of node to be deleted. (temp)

e. Traverse in node based on the value of position-1 by running a loop.

f. We need to delete temp  → next, free it and unlink the deleted node.

g. If position is more than number of nodes, just return.

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
    int data;
    struct LLNode* next;

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
        //O(1) constant time
//display linked list
void display(struct LLNode**node)
    struct LLNode *temp= *node;
            temp=temp->next; //move to next node
        //O(number of nodes)

//function to delete node at given pos
void deleteNode(struct LLNode **head_ref, int pos)
   if (*head_ref == NULL)
   //temp to store head
   struct LLNode* temp = *head_ref;
   //Delete head node
    if (pos == 0)
        *head_ref = temp->next; 
    //store previous of to be deleted node
    for (int i=0; temp!=NULL && i<pos-1; i++)
        temp = temp->next;
    if (temp == NULL || temp->next == NULL)
    //delete node at pos (next of pos-1)
    struct LLNode *next = temp->next->next;
    temp->next = next; 

//Main function
int main()
    //Input list
    struct LLNode* head = NULL;
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 2);
    cout<<"Input linked list: ";
    int k;
    cout<<"Enter pos to be deleted: ";
    //delete node at pos k
    deleteNode(&head, k);

    cout<<"Output linked list: ";
    return 0;

READ  Detect a loop in the Linked List


Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions