Some LinkedList Related Problems-2

Reverse A Doubly Linked List.

void addNode(struct node **head_ref,int pos,int data)
{
        node *current=*head_ref;
        while(pos)
        {
            current=current->next;
            pos--;
        }
        node *tmp=new node;
        tmp->data=data;
        tmp->prev=current;
        tmp->next=current->next;
        current->next=tmp;
}

Prints the nodes having no siblings.

/* Tree node structure  used in the program
 struct Node
 {
     int data;
     struct Node* left, *right;
}; */

void printSibling(struct Node* node)
{
   // Your code here
   if(node==NULL)
   return;
   int v= node->data;
   Node *lft=node->left;
   Node *rit=node->right;
   if(lft==NULL && rit!=NULL)
   {
       printf("%d ",rit->data);
       printSibling(rit);
   }
   else if(lft!=NULL && rit==NULL)
   {
       printf("%d ",lft->data);
       printSibling(lft);
   }
   else
   {
       printSibling(lft);
       printSibling(rit);
   }
}

Check A LinkedList is circular or not.

/* Link list Node
struct Node {
    int data;
    struct Node* next;
}; */


/* Should return true if linked list is circular, else false */
bool isCircular(struct Node *head)
{
   // Your code here
   if(head==NULL)
   return true;
   else
   {
       Node *node=head;
       Node *nxt=node->next;
       while(nxt!=head)
       {
           if(nxt==NULL)
           return false;
           nxt=nxt->next;
       }
       return true;
   }
   return true;
}

Find The Middle Node.

/* Link list Node
struct Node {
    int data;
    struct Node* next;
}; */

/* Should return data of middle node. If linked list is empty, then  -1*/
int getMiddle(struct Node *head)
{
   // Your code here
   if(head==NULL)
   return -1;
   int total=1;
   int arr[105];
   arr[total]=head->data;
   head=head->next;
   while(head!=NULL)
   {
       total+=1;
       arr[total]=head->data;
       head=head->next;
   }
   if(total%2)
   return arr[(total+1)/2];
   else
   return arr[total/2+1];
}

Problem Link

Merge two sorted list.

//Merge 2 sorted list
/* Link list Node
struct Node {
    int data;
    struct Node* next;
}; */

struct Node* SortedMerge(struct Node* head1,  struct Node* head2)
{
    // Your Code Here
    Node *tmp1=head1,*tmp2=head2;
    Node *head=new Node;
    Node *tmp;
    bool f=0;
    while((tmp1!=NULL) || (tmp2!=NULL))
    {
        if(tmp1==NULL)
        {
            while(tmp2)
            {
                tmp->next=tmp2;
                tmp=tmp->next;
                tmp2=tmp2->next;
            }
        }
        else if(tmp2==NULL)
        {
            while(tmp1)
            {
                tmp->next=tmp1;
                tmp=tmp->next;
                tmp1=tmp1->next;
            }
        }
        else if((tmp1!=NULL) && (tmp2!=NULL))
        {
            if(tmp1->data<=tmp2->data)
            {
                if(f==0)
                {
                    head->data=tmp1->data;
                    tmp=head;
                    f=1;
                }
                else
                {
                    tmp->next=new Node;
                    tmp=tmp->next;
                    tmp->data=tmp1->data;
                }
                tmp1=tmp1->next;
            }
            else
            {
                if(f==0)
                {
                    head->data=tmp2->data;
                    tmp=head;
                    f=1;
                }
                else
                {
                    tmp->next=new Node;
                    tmp=tmp->next;
                    tmp->data=tmp2->data;
                }
                tmp2=tmp2->next;
            }
    }
        }

    return head;
}

Problem Link

Delete the middle node.

/* Link list Node
struct Node
{
    int data;
    struct Node* next;
}; */

// Deletes middle of linked list and returns head of the modified list
struct Node* deleteMid(struct Node *head)
{
     // Your Code Here
     int arr[1001];
     int idx=0;
     Node *tmp=head;
     while(tmp)
     {
         idx+=1;
         tmp=tmp->next;
     }
     if(idx==0)
     return head;
     if(idx==1)
     return head=NULL;
     idx=idx/2+1;
     tmp=head;
     Node *prev;
     idx-=1;
     while(idx)
     {
         idx-=1;
         prev=tmp;
         tmp=tmp->next;
     }
     prev->next=tmp->next;
     return head;
}

Problem Link

Reverse a doubly linkedlist.

/* a node of the doubly linked list */
/*struct node
{
  int data;
  struct node *next;
  struct node *prev;
};*/
void reverse(struct node **head_ref)
{
  // Your code goes here
  node *tmp=(*head_ref);
  node *nxt,*prv;
  node *prev;
  while(tmp)
  {
      nxt=tmp->next;
      prv=tmp->prev;

      tmp->prev=nxt;
      tmp->next=prv;

      prev=tmp;
      tmp=nxt;
  }
  (*head_ref)=prev;
}