GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
63 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 by Veteran (280k points)   | 63 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

+9 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_D.next------> Address_of_F

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
answered by Veteran (45.3k points)  
selected by
Your logic is awesome ! Try for part a too !
Top Users Feb 2017
  1. Arjun

    5278 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3942 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1660 Points

Monthly Topper: Rs. 500 gift card

20,857 questions
26,009 answers
59,671 comments
22,107 users