GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
74 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 (283k points)   | 74 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.8k points)  
selected by
Your logic is awesome ! Try for part a too !


Top Users Apr 2017
  1. akash.dinkar12

    3514 Points

  2. Divya Bharti

    2546 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,042 answers
63,234 comments
24,135 users