Mündəricat
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;
}