Bağlı bir siyahını yerində yenidən düzəldin

Bağlı bir siyahı verilmişdir L0-> L1->… -> Ln-1-> Ln. Siyahıda olan qovşaqları yenidən düzəldin ki, yeni formalaşan siyahı: L0-> Ln-> L1-> Ln-1-> L2-> Ln-2…

misal

GİRİŞ:
1-> 2 -> 3 -> 4 -> 5

Çıxış:
1 -> 5 -> 2 -> 4 -> 3

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

Alqoritm

1. Tısbağa və dovşan metodundan istifadə edərək orta nöqtəni tapın
    a. İki dəyişəni yavaş, sürətli götürün. İki addım qabaqda sürətlə hərəkət edin və hər təkrarlama üçün yalnız bir addım qabaqda yavaş hərəkət edin.

     b. Siyahının sonunda yavaş, əlaqəli siyahının orta nöqtəsini göstərəcəkdir

2. Bağlı siyahını orta nöqtədən istifadə edərək iki yarıya bölün

3. İkinci yarıyı tərsinə çevirin

4. Birinci və ikinci yarıların alternativ birləşməsini edin

Yuxarıdakı nümunə üçün Alqoritmin tətbiqi

1. Orta nöqtə 3 qovşağıdır

2. list1 = 1-> 2-> 3, list2 = 4-> 5

3. İkinci siyahını tərsinə çevirin.
list1 = 1-> 2-> 3, list2 = 5-> 4

4. Alternativ Birləşdirmə
nəticə = 1 -> 5 -> 2 -> 4 -> 3

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
	int data;
	LLNode *next;	
};
// Function to create newNode in a linkedlist
LLNode* newNode(int data)
{
    LLNode *temp = new LLNode;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
// Function to reverse the linked list
void reverselist(LLNode **head)
{
    // Initialize prev and current pointers
    LLNode *prev = NULL, *curr = *head, *next;
 
    while (curr)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
 
    *head = prev;
}
// Function to rearrange a linked list
void rearrange(LLNode **head)
{
    // 1) Find the middle point using tortoise and hare method 
    LLNode *slow = *head, *fast = slow->next;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
 
    // 2) Split the linked list in two halves
    LLNode *list1 = *head;
    LLNode *list2 = slow->next;
    slow->next = NULL;
 
    // 3) Reverse the second half
    reverselist(&list2);
 
    // 4) Merge alternate nodes
    *head = newNode(0); // Assign dummy Node
 
    // curr is the pointer to this dummy Node, which will
    // be used to form the new list
    LLNode *result = *head;
    while (list1 || list2)
    {
        // First add the element from first list
        if (list1)
        {
            result->next = list1;
            result = result->next;
            list1 = list1->next;
        }
 
        // Then add the element from second list
        if (list2)
        {
            result->next = list2;
            result = result->next;
            list2 = list2->next;
        }
    }
    // Assign the head of the new list to head pointer
    *head = (*head)->next;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node with this data and next pointing to NULL
	curr->data=dataToBeInserted;
	curr->next=NULL;

	if(*head==NULL) //if list is empty then set the current formed node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	while(temp!=NULL) //till the list ends (NULL marks ending of list)
		{
			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() 
{    
	
	LLNode *head = NULL; //initial list has no elements

	insertAtBeginning(&head,5);
	insertAtBeginning(&head,4);
	insertAtBeginning(&head,3);
	insertAtBeginning(&head,2);
	insertAtBeginning(&head,1);
	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	rearrange(&head);
	cout<<"After rearranging the elements"<<endl;
	display(&head);
	return 0;
}

 

Şərh yaz

Translate »