Alternativ mövqelərdə əlaqəli bir siyahını digərinə birləşdirin

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

A və B əlaqəli iki siyahını nəzərə alaraq, A siyahısının alternativ mövqelərində B qovşaqlarını A-ya daxil etməliyik.

misal

Zamanın mürəkkəbliyi: O (n),

n - ilk siyahıdakı qovşaq sayı.

Alqoritm

a. ListA-da mövcud mövqelər olmayana qədər keçin.
b. ListB-də dövr edin və ListB-nin qovşaqlarını ListA-ya daxil edin
c. Göstəriciləri dəyişdirərək əlavə edin.
d. Həm A həm də B növbəti göstəricilərini saxlayın.
e. B işarəsini A göstəricisinin yanında, B göstəricisinin sonrakı hissəsini A göstəricisinin yanında edin, bunu etməklə ListA-ya ListB düyünü əlavə edirik.
f. ListA və ListB göstəricilərini hərəkət etdirin.

Alqoritm işləyir

C ++ Proqramı

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};


/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    if (temp==NULL)
    {
        cout<<"Empty linked list"<<endl;
    }
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<" ->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

void Merge(struct LLNode *A, struct LLNode **B)
{
     struct LLNode *current_inA = A, *current_inB = *B;
     struct LLNode *next_inA, *next_inB;
   
     while (current_inA != NULL && current_inB != NULL)
     {
         //store next pointers of current pointers
         next_inA = current_inA->next;
         next_inB = current_inB->next;
         //adding node from B to A by changing:
         //next of node in B to next in A
         //move pointers
         current_inB->next = next_inA;  
         current_inA->next = current_inB;  
         current_inA = next_inA;
         current_inB = next_inB;
    }
    //change pointer of head of list B
    //remaining nodes
    *B = current_inB;
}
 
// Driver program to test above functions
int main()
{
     struct LLNode *ListA = NULL, *ListB = NULL;
     insertAtBeginning(&ListA, 8);
     insertAtBeginning(&ListA, 7);
     insertAtBeginning(&ListA, 6);
     
     insertAtBeginning(&ListB, 5);
     insertAtBeginning(&ListB, 4);
     insertAtBeginning(&ListB, 3);
     insertAtBeginning(&ListB, 2);
     insertAtBeginning(&ListB, 1);

     cout<<"Linked List A: ";
     display(&ListA);
 
     cout<<"Linked List B: ";
     display(&ListB);
    
     cout<<"Merging List B into List A at alternate positions in A";
     Merge(ListA,&ListB);
 
     cout<<"\nOutput Linked List A: ";
     display(&ListA);
 
     cout<<"Output Linked List B: ";
     display(&ListB);
 
     return 0;
}

 

Crack Sistemi Dizayn Müsahibələri
Translate »