Question

write a method which takes 3 arguments - a pointer to a linked list of integers, and two integers n and j - and inserts n after the jth. element of the list. if j is 0, n is inserted at the head of the list. If j is greater than the number of element in the list, n is inserted after the last one

Answer 1

Code:

#include<iostream>
#include<stdlib.h>
using namespace std;
struct node
{
   int a;
   struct node *next;
};
void insert(struct node **p, int n, int j)
{
   struct node *nn=(struct node*)malloc(sizeof(struct node));//creating memory for node
   nn->a=n;nn->next=NULL;//storing data
   if(j==0)
   {
       nn->next=*p;*p=nn;//new node is attached in front of original list
   }
   else
   {
       int i;struct node *t1=*p, *t2=*p;//2 pointers t1 and t2 to track positions
       for(i = 0; t1 != NULL; i++, t2 = t1, t1 = t1 -> next)//just before t1 is updated t2 takes its value
       {
           if(i == j) break;
       }
       if(t1==NULL)//if no of nodes are less than j
       {
           t2->next=nn;return;
       }
       nn->next=t1;
       t2->next=nn;
   }
}
void display(struct node **p)//displays list
{
   for(struct node *temp=*p;temp != NULL;temp=temp->next)
   {
       cout<<temp->a<<" ";
   }
   cout<<endl;
}
int main()
{
   struct node *p;
   p=(struct node *)malloc(sizeof(struct node));
   p->a=1;
   p->next=NULL;
   while(1)
   {
       cout<<"enter 0 to break, 1 to continue "<<endl;
       int ch;cin>>ch;
       if(ch==0) break;
       cout<<"enter integer and position"<<endl;
       int num, pos;cin>>num>>pos;
       insert(&p, num, pos);display(&p);
   }
   return 0;
}

Output:

enter to break, 1 to continue enter integer and position 20 2 1 enter to break, 1 to continue enter integer and position 31 2 31 enter to break, 1 to continue enter integer and position 4 3 2 3 1 4 enter to break, 1 to continue enter integer and position 5 8 2 3 1 4 5 enter to break, 1 to continue enter integer and position 61 2 6 3 1 4 5 enter to break, 1 to continue enter integer and position 72 2 6 7 3 1 4.5 enter to break, 1 to continue enter integer and position 84 2 6 7 3 8 1 4 5 enter to break, 1 to continue enter integer and position 9 13 2 6 7 3 8 1 4 5 9 enter to break, 1 to continue Process exited after 54.27 seconds with return value o Press any key to continue ...