Problem
Delete a node in the middle of list, given only access list once.
Solution
1. Find the node to be deleted.
2. Modify the value of the node to that of next node.
3. Modify the reference pointer to the next next node.
4. Delete the next node.
#include <iostream>
using namespace std;
typedef struct linked_list{
int data;
struct linked_list *next;
}Linked_list;
int add_node(Linked_list **head, int d)
{
Linked_list *l = new Linked_list;
if(l == NULL) return 0;
Linked_list *t = *head;
l->data = d;
l->next = NULL;
if(*head == NULL){
*head = l;
return 1;
}
while(t->next != NULL){
t = t->next;
}
t->next = l;
return 1;
}
void del_mid_elem(Linked_list *head, Linked_list *l)
{
Linked_list *t;
if(head->next == NULL && head->next == NULL){
return;
}
t = l->next;
l->data = l->next->data;
l->next = l->next->next;
delete t;
}
void delete_list(Linked_list *head)
{
while(head != NULL){
Linked_list *t = head->next;
delete head;
head = t;
}
}
int main(int argc, char* argv[])
{
Linked_list *head = NULL;
Linked_list *l;
add_node(&head, 1);
add_node(&head, 1);
add_node(&head, 2);
add_node(&head, 3);
add_node(&head, 9);
add_node(&head, 4);
add_node(&head, 1);
add_node(&head, 5);
cout << "before" << endl;
l = head;
while(l!=NULL){
cout << l->data << endl;
l = l->next;
}
l = head;
while(l!=NULL){
if(l->data == 9) break;;
l = l->next;
}
cout << "after deleting " << l->data << endl;
del_mid_elem(head, l);
l = head;
while(l!=NULL){
cout << l->data << endl;
l = l->next;
}
delete_list(head);
return 0;
}
Output
before
1
1
2
3
9
4
1
5
last 0 in the list
last 1 in the list
5
last 2 in the list
1
5