Mündəricat
Verilən əlaqəli siyahıda, siyahı dəyişən artan və azalan əmrlərdədir. Siyahını sıralamaq üçün səmərəli bir həll yazmalıyıq.
misal
Zamanın mürəkkəbliyi: O (n)
Alqoritm
a. Bağlı siyahını iki ayrı əlaqəli siyahıya ayırmaq lazımdır, bir əlaqəli siyahı tək mövqe elementləri, digəri cüt ilə.
b. Azalan sırayla siyahını tərsinə çeviririk. (əks funksiyanı istifadə edin)
c. Hər iki siyahını birləşdiririk.
1. Yüksələn və enənlərin başlarını müqayisə edin.
2. Giriş başını hər iki siyahının daha böyük başlığı ilə əvəzləyirik və LL daxilində və əlavə edilmiş sayda baş mövqeyini hərəkət etdiririk.
C ++ Proqramı
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode *next;
};
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
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 curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
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;
}
void ReverseLL(LLNode *&head)
{
struct LLNode* prev = NULL, *curr = head, *next;
while(curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
//O(number of nodes)
head = prev;
}
// A utility function to merge two sorted linked lists
struct LLNode *MergeLL(struct LLNode *head1,struct LLNode *head2)
{
if(head1 == NULL)
{
return head2;
}
if(head2 == NULL)
{
return head1;
}
struct LLNode *temp = NULL;
if (head1->data < head2->data)
{
temp = head1;
head1->next = MergeLL(head1->next, head2);
}
else
{
temp = head2;
head2->next = MergeLL(head1, head2->next);
}
return temp;
}
//Split function
void Split(struct LLNode *head,struct LLNode **head1,struct LLNode **head2)
{
//Initialize with zero heads
insertAtBeginning(&*head1, 0);
insertAtBeginning(&*head2, 0);
struct LLNode *ascending = *head1;//head1 with ascending list
struct LLNode *descending = *head2;//head2 with descending list
struct LLNode *curr = head;
while(curr)
{
ascending->next = curr;
ascending = ascending->next;
curr = curr->next;
if(curr)
{
descending->next = curr;
descending = descending->next;
curr = curr->next;
}
}
ascending->next = NULL;
descending->next = NULL;
//Remove zeroes
*head1 = (*head1)->next;
*head2 = (*head2)->next;
}
//function to sort
void Sort(struct LLNode **head)
{
struct LLNode *headAscn , *headDscn;
//Split into 2 listss
Split(*head, &headAscn, &headDscn);
ReverseLL(headDscn);
*head = MergeLL(headAscn, headDscn);
}
//Main function
int main()
{
struct LLNode *head = NULL;
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 50);
insertAtBeginning(&head, 40);
insertAtBeginning(&head, 30);
insertAtBeginning(&head, 60);
insertAtBeginning(&head, 10);
cout<<"Input linked list is: ";
display(&head);
Sort(&head);
cout<<"\nOutput linked list is: ";
display(&head);
return 0;
}
