174 views
Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.
asked in DS | 174 views
// node is a struct containing an int and next pointer
void insert(int D, node* p){
node* temp = (node*)malloc(sizeof(node));
temp->next = p->next; // make temp point to the node where p was pointing
p->next = temp; // attach node temp next to node p
/*till this point it is simialr to inserting node after a node
whose pointer p is given. Now change the data of both nodes p and temp to get desired result*/
temp->data = p->data; // copy the data of current node to new node
p->data = D;
}


let A,B,C,D,E,F be the data ..
A---> B ----> C----> E ---->F
let pointer to E be p..
a node with data D has to be inserted before E..
i ll do one thing , add D just after node E .. it ll take constant time..

A---> B ----> C----> E -----> D---->F

take a temporary variable and swap the value E and D..
temp = p.data
p.data= p.next.data
p.next.data= temp
now linked list wil look like ..
A---> B ----> C----> D-----> E ---->F
still one more work left.. now pointer p pointing to D so increment pointer p to point data E..
p= p--->next
selected by
Your logic is awesome ! Try for part a too !