GATE1999-11b

1.2k 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.
in DS
29
// 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;
}

0
good one @ mcjoshi

Let $A,B,C,D,E,F$ be the data.
$A \rightarrow B \rightarrow C \rightarrow E \rightarrow 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$ and it'll take constant time.
$p.{next} \rightarrow Address\_of\_D$
$Address\_of\_D.next \rightarrow Address\_of\_F$

$A \rightarrow B \rightarrow C \rightarrow E \rightarrow D \rightarrow F$

Take a temporary variable and swap the values $E$ and $D$..
$temp = p.data$
$p.data= p.next.data$
$p.next.data= temp$

Now linked list wil look like
$A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F$
still one more work left - now pointer $p$ pointing to $D$ so increment pointer $p$ to point data $E$.
$p= p \rightarrow next$

void InsertBeforeGivenPointer(struct node* p, int D){
struct node* temp = (node*)malloc(sizeof(struct node));
temp->next = p->next;
p->next = temp;
temp->data = p->data;
p->data = D;
}

edited
1
Your logic is awesome ! Try for part a too !
3

this should be there:

0
Wat a soluchan :p  =D
0
@srestha

This will also work if p is pointing to last node?
Suppose initially we have LL : A,B,C

p points to B

new node: B1

Now,

B1->next = p->next;

p->next = B1

This will give the LL: A,B,B1,C

Now swap the values of B and B1

temp = p->value

p->value = B1->value

B1→value=temp

This will make the LL: A,B1,B,C

Related questions

1
2.1k views
In binary tree, a full node is defined to be a node with $2$ children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves. Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap: $7, 6, 5, 4, 3, 2, 1$. Show the result after the deletion of the root of this heap.