Datasructures material page2

                              Datastructures material and frequently asked questions in interview
 
                                                                          page2:

  Finding kth node from last in a linked list
       
   Algorithm:
         
           take two pointer at start of linked list traverse first pointer for k nodes
           and then move both the points untill first pointer reach end of linklist by that time 
           second  pointer will reach to kth node from last
    
   Code:
                     

int findkthlast(struct node *head)

  {

       int i=0,j,k;

       struct node *temp=head->next;

       printf("enter which node u want to find from last");

       scanf("%d",&j);

       while(temp!=NULL)

       {

        i++;

        temp=temp->next;

       }

       temp=head->next;

       for(k=0;k<i-j;k++)

       {

       temp=temp->next;

       }

       printf("%d is %d node from last",temp->data,j);

       return 0;

 }     

 

 How to find loop in linked list

 Algorithm:

     Take pointer at start and move one pointer two nodes at a time and other pointer one node

      if there exist any loop surely at one point of these two pointers will meet at same nodes

 Code:

 

void detectloop(struct node *head)

      {

            struct node *slow,*fast;

            slow=fast=head->next;

            do

            {

                  slow=slow->next;

                  fast=fast->next->next;

             }while(fast!=slow&&fast!=NULL);

                  if(fast==NULL)

                  printf("\n no loop present in given list");

                  else

                  printf("\n loop present in given list");

                 

       }

How remove loop in linked list:

 Algorithm:

   if two students running in loop if one student running 

   at a speed double of other they surely meet at start of 

   of race

   in the same way

   so take two pointer move first pointer two nodes and other 

   one node agian if there is loop these two will meet a point

   then take third pointer at start of linked list and move 

   third and second pointer untill thier next node will be equal 

   so we can simply remove link from second pointer

code:

  

 

void removeloop(struct node *head)

      {

            struct node *slow,*fast,*temp;//temp is third pointer

            slow=fast=head->next;

            do

            {

                  slow=slow->next;

                  fast=fast->next->next;

                  }while(fast!=slow&&fast!=NULL);

                 

            fast=head->next;

            while(fast!=slow)

            {

                  fast=fast->next;

                  temp=slow;

                  slow=slow->next;

                  }

                  temp->next=NULL;

                  printf("loop removed successfully");

            }//end of loop remove


  Inserting in sorted order:

Algorithm:

maintain two pointers for previous and next if we are inserting increse order when find element greter than the given number maintain previous node and keep previous next as newly created node and newly created next as current node 

Code:
 

void insertsort(struct node *head,int i)

{

      struct node *temp,*q,*t;

      if(head->next==NULL)

      {

temp=(struct node *)malloc(sizeof(struct node));

      temp->data=i;

      temp->next=NULL;

      head->next=temp;

      printf("inserted when head is null");

     

    }

           

      else

      {

            temp=(struct node *)malloc(sizeof(struct node));

            temp->data=i;

            temp->next=NULL;

            t=head;

            q=head->next;

            while(i>q->data&&q->next!=NULL)

            {

            t=q;

            q=q->next;

           }

           if(i<=q->data)

           {

           t->next=temp;

           temp->next=q;

            }

            else if(q->next==NULL)

            {

                  q->next=temp;

                  }

            printf("inserted when head is not null");

           

      }

}/