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


Top Users May 2017
  1. akash.dinkar12

    3548 Points

  2. pawan kumarln

    2126 Points

  3. Bikram

    1922 Points

  4. sh!va

    1682 Points

  5. Arjun

    1622 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1270 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1028 Points

  10. Arnab Bhadra

    812 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    752 Points

  3. Arnab Bhadra

    726 Points

  4. akash.dinkar12

    428 Points

  5. Arjun

    350 Points


22,896 questions
29,206 answers
65,329 comments
27,708 users