Tək bir əlaqəli siyahını tərsinə çevirin (təkrarlayan / qeyri-rekursiv)

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ıda olan bütün elementləri tərsinə çevirmək və yeni əlaqəli siyahını göstərmək üçün bir proqram yazın [Qeyri-Rekursiv / İterativ]

misal

Giriş: 23 -> 1 -> 12 -> 15 -> 23 -> 49 -> 23 -> XNUMX
Çıxış: 23 -> 49 -> 23 -> 15 -> 12 -> 1 -> 23 -> XNUMX

Bu, əlaqəli bir siyahını geri çevirmək üçün təkrarlanan bir üsuldur, bu metodda əvvəlki ilə əvvəlki, əvvəlki ilə indiki və sonrakı kimi dəyişdiriləcəkdir. Bunu aşağıdakı diaqramda açıq şəkildə izah etmək olar.

Bağlı bir siyahının dəyişdirilməsinin həyata keçirilməsi

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

Alqoritm

1. Üç keçid yaradın (məsələn: temp, prev və curr), burada temp əlaqəli siyahıdan keçmək, əvvəlki qovluğu və cari düyün üçün cərgəni saxlamaq üçün əvvəlcədəndir.

2. Bağlı siyahının sonuna qədər,
a. Temp göstəricisini, yəni temp = curr-> next irəliləyin
b. Next hər bir düyün üçün əvvəlki hala gəlir, yəni curr-> next = prev
c. indiki, yaxınlaşan düyün üçün əvvəlki olur, yəni prev = curr
d. cərəyanı növbəti qovşağa keçirin, yəni curr = temp

3. Son elementi əlaqəli siyahının rəhbəri kimi düzəldin, yəni * baş = əvvəl

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
}

void reverseListIteratively(struct LL **head)
{
	struct LL *temp=NULL,*prev=NULL,*curr=*head; //temp for temporary head , prev to store previous node , curr for current node
	while(curr!=NULL)
	{
	    temp=curr->next; //advance the temp 
		curr->next=prev; //next becomes the previous for every node
		prev=curr; //present becomes previous for the upcoming node
		curr=temp; //move the current to next node
	}
  *head=prev;
	//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,23);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,12);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	cout<<"Initial List is :-\n";
	display(&head);
	
	reverseListIteratively(&head);
	
	cout<<"\nAfter the reverse function the list is :- \n";
	display(&head);
	
	return 0;
}

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