Sondan Bağlı siyahının n-ci qovşağı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 sonundan n-cü elementi tapmaq üçün bir proqram yazın

misal

Input:  6->16->15->50->1->23->49, N= 3

Çıxış: 1

Burada sondan 3-cü element 1-dir

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

burada n - əlaqəli siyahının uzunluğu.

Alqoritm

Bu, əlaqəli bir siyahının sonundan n-cü elementi tapmaq üsullarından biridir
1. Birincisi, ikincisi iki göstərici yaradın və onları əlaqəli siyahının başına gətirin
2. İkinci göstəricini N addımlarla hərəkət etdirin
3. Null-a bərabər olmayan saniyə-> qədər, birinci və ikinci göstəricini bir addım qabağa çəkin.
4. əvvəlcə sondan n-ci elementdir.

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
}

struct LL* nthNodeFromEnd(struct LL**head,int n)
{
struct LL*first=*head , *second = *head;
	for(int i=1;i<n;i++) // increase second pointer ahead by n steps
		{
			if(second)
				second=second->next;
			else
				break;
		}
	if(second == NULL)
	{
		cout<<"List has less than specified number of nodes\n";
		return NULL;	
	}	
	while(second->next!=NULL) //increase by one steps now till we reach the last node and now the first will point to Nth from end
	{
		first = first->next;
		second = second->next;
	}
	
return first;
}


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);
	
	display(&head);
	
	int N = 3; //number of node whose value is to be known
	
	struct LL * NthFromEnd =  nthNodeFromEnd(&head,N);
	if(NthFromEnd == NULL)
		{	}
	
	else
	cout<<N<<" th node from end is "<<NthFromEnd->data<<endl;
	
	return 0;
}

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