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

### Example

**Time complexity : O (n)**

**Algorithm**

**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 else { curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head *head=curr; } //O(1) constant time } //display linked list void display(struct LLNode**node) { struct LLNode *temp= *node; while(temp!=NULL) { if(temp->next!=NULL) cout<<temp->data<<"->"; else cout<<temp->data; temp=temp->next; //move to next node } //O(number of nodes) cout<<endl; } //function to delete node at given pos void deleteNode(struct LLNode **head_ref, int pos) { // if (*head_ref == NULL) { return; } //temp to store head struct LLNode* temp = *head_ref; //Delete head node if (pos == 0) { *head_ref = temp->next; free(temp); return; } //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) { return; } //delete node at pos (next of pos-1) struct LLNode *next = temp->next->next; free(temp->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: "; display(&head); int k; cout<<"Enter pos to be deleted: "; cin>>k; //delete node at pos k deleteNode(&head, k); cout<<"Output linked list: "; display(&head); return 0; }