Bağlı Siyahının son elementini ilk yerdə hərəkət etdirin

Verilən əlaqəli siyahıda son elementi əlaqəli siyahının önünə keçirmək üçün bir proqram yazın

misal

Bu şəkildə, son qovluğu verilmiş əlaqəli siyahının ön hissəsinə keçiririk.

Alqoritm

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

1 Adım: əlaqəli siyahını arqument kimi qəbul edən və son elementi öndə olan yeni bir əlaqəli siyahı verən bir funksiya yaradın.
2 Adım: Son düyünə qədər keçin.
a) Həm son, həm də ikinci son qovluğu saxlayın.
3 Adım: İkinci son nodu son node kimi et.
a) saniyənin sonrakı hissəsini NULL kimi göstərin, çünki hərəkət etdikdən sonra son node olacaq.
4 Adım: Sonuncunu baş kimi et.
a) last-> next = * baş, son düyünü baş kimi növbəti edir.
5 Adım: Son düyünü baş düzəldin.
a) Bu, baş göstəricisini son vəziyyətə gətirərək verilmişdir.
6 Adım: verilmiş əlaqəli siyahıdakı funksiyanı çağırın. Başlıq olaraq son olaraq yeni bir əlaqəli siyahı çap edəcəkdir.

Alqoritm işləmə nümunəsi

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 moveLastNode(struct LL **head) 
{
	struct LL *temp = *head;
	struct LL * last , *secondLast;
	
	while(temp->next->next != NULL) // traverse till second last node
		temp = temp->next;
	
	secondLast = temp;
	last = temp->next;
	
	secondLast->next = NULL; //make the next of second last as NULL as after moving it will become the last node
	last->next = *head; //make the last node's next as head
	
	*head = last; //make the last node the head
	
}

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);
	cout<<"The list initially is :-\n";
	display(&head);
	
	moveLastNode(&head);
	cout<<"\nAfter moving last node to front the list becomes :-\n";
	display(&head);
	
	return 0;
}

Şərh yaz

Translate »