1. Delete a node at a given position
2. Delete whole single linked list recursively.
1. Delete a node at a given position
If the head node is to be deleted, then delete the head node and point the new head to the next element in the LL.
If the element in the middle is to be deleted:
- Then take the temp pointer to the previous node of the node to be deleted.
- Take a next pointer pointing to the next of the node to be deleted.
- Delete the node.
- Assign the temp->next to the next node.
2. Delete whole single linked list recursively.
1. If the head node is null return it.
2. Else move the head to next node and recursively call the function.
Solution in C++
#include<iostream> #include<vector> #include<string> using namespace std; struct Node { int data; Node *next; Node(int x) { data = x; next = NULL; } }; void print_list(Node *head) { Node *start = head; while(start) { cout<<start->data<<" -> "; start = start->next; } cout<<"\n"; } void delete_given_node(Node **head, int node_pos) { if (*head == NULL) return; Node *temp = *head; // If head needs to be removed if (node_pos == 0) { *head = temp->next; // Change head free(temp); // free old head return; } // Find previous node of the node to be deleted for (int i=0; temp!=NULL && i<node_pos-1; i++) temp = temp->next; // Node temp->next is the node to be deleted // Store pointer to the next of node to be deleted Node *next = temp->next->next; free(temp->next); temp->next = next; } void delete_full_list(Node *head) { if(head == NULL) return; delete_full_list(head ->next); free(head); } int main() { Node *head = new Node(2); head -> next = new Node(1); head -> next -> next = new Node(4); head -> next -> next -> next = new Node(3); head -> next -> next -> next -> next = new Node(6); head -> next -> next -> next -> next -> next = new Node(5); cout<<"The original list = "<<endl; print_list(head); int node_no = 3; delete_given_node(&head, node_no); cout<<"Thelist after deleting "<< node_no <<" node is = "<<endl; print_list(head); delete_full_list(head); return 0; }