Bağlı Siyahının ortasını tapın

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.

Bağlı bir siyahı verildikdə, əlaqəli siyahının ortasını tapmaq üçün bir proqram yazın

misal

Giriş: 6->16->15->50->1->23->49

Çıxış: 50

Giriş: 6->16->15->50->1->23

Çıxış: 50

Bu, Bağlı Siyahının ortasını tapmaq üsullarından biridir

Zaman Mürəkkəbliyi: O (n)

Alqoritm

Tısbağa Alqoritmi
1. Yavaş və sürətli iki göstərici yaradın, onları başa düzəldin
2. Sürətli və sürətli qədər -> sıfıra bərabər deyil
3. Yavaş göstəricini bir addım və sürətli göstəricini əlaqəli siyahı boyunca iki addım hərəkət etdirin
4. orta element olan yavaş göstərici elementini qaytarın

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

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


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		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 current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

int middleOfList(struct LL**head)
{
	
	struct LL*slow=*head,*fast=*head;
	while(fast&&fast->next) //if fast not NULL and fast's next is not NULL because it takes two steps
		{
			slow=slow->next; //move this with speed x
			fast=fast->next->next; //move this with speed 2x
		}
	return  slow->data; //middle of list
	//O(number of nodes)
}


void display(struct LL**head)
{
	struct LL*temp=*head;
	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;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	//insertAtBeginning(&head,49);
	
	display(&head);
	
	cout<<"Middle of List is "<<middleOfList(&head)<<endl;
	
	return 0;
}

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