First time here? Checkout the FAQ!
+6 votes
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 by Veteran (295k points)   | 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;

1 Answer

+12 votes
Best answer
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..
Pnext --->Address_of_D> Address_of_F

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

take a temporary variable and swap the value E and D..
temp = 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
answered by Veteran (47.2k points)  
selected by
Your logic is awesome ! Try for part a too !

Top Users Sep 2017
  1. Habibkhan

    7838 Points

  2. Warrior

    2812 Points

  3. Arjun

    2696 Points

  4. rishu_darkshadow

    2692 Points

  5. A_i_$_h

    2456 Points

  6. manu00x

    2040 Points

  7. nikunj

    1980 Points

  8. Bikram

    1864 Points

  9. makhdoom ghaya

    1790 Points

  10. SiddharthMahapatra

    1718 Points

26,243 questions
33,815 answers
31,168 users