Tuesday, November 15, 2016

Linked list problems

Here the list of questions about linked list

typedef struct node
{
     struct node* link ;
     int data ;
}node ;

static void reverse(node** head)
{
     node* cur = *head ;
     node* prev = NULL ;
     node* next = cur->next ;
     while (cur->next != NULL)
     {
             next = cur->next ;
             cur->next = prev ;
             prev = cur ;
             cur = next ;
       }
     *head = prev ;
}


// Remove nth node from list
void remove_nth_from_last(node** head, int n)
{
       node* cur = head ;
       while (n--)
           cur = cur->next ;
      node* slow = head ;
      while (cur->next != NULL)
      {
            cur = cur->next ;
            slow = slow ->next ;
       }

   // slow now points the node pointing from last nth node
   node* temp = slow ;
   temp->next = slow ->next ;
   temp->data = slow->next->data ;
   free(slow) ;
}

node* merge_sorted_list(node* l1, node* l2)
{
    node head = (node*) getnode(0) ;
    node* tail = &head ;
    while (l1->next != NULL && l2->next != NULL)
    {
            if (l1->val < l2->val)
           {
                 tail ->next = getnode(l1->val) ;
                 l1 = l1->next ;
            }
            else
            {
                tail->next = getnode(l2->val) ;
                 l2 = l2->next ;
            }
            tail = tail->next ;
  }
  if (l1->next)?tail->next = l1 : tail->next = l2 ;
  return head->next ;
}

// return
// 0 -- loop not found
// 1 -- loop found
int detect_loop(node* head)
{
    if (head == NULL)
           return 0 ;
   node* slow = head, *fast = head ;
   while (fast->link != NULL)
   {
              if (fast->link == NULL)
                       return 1 ;
              if (slow == fast)
                    return 1 ;
              fast = fast->link ;
              if (slow == fast)
                    return 1 ;
             slow = slow->next ;
             fast = fast->next ;
    }
    return 0;
}

      
             

           

No comments:

Post a Comment