Bağlı siyahının palindrom olub olmadığını yoxlayın

Bir-birinə bağlı bir siyahı verildikdə, palindrom olub olmadığını tapın

Palindrom: irəli və geriyə doğru oxuyan bir tam və ya bir simli.

misal

Alqoritm

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

1 Adım: Verilmiş əlaqəli siyahının ortasını alın.

a) İki saxta əlaqəli siyahı yaradın (sürətli və yavaş).
b) Yavaş və sürətli verilmiş əlaqəli siyahıların surətləridir.
c) Siyahılar arasında elə sürüşün ki, sürətli-> next = null qədər iki mövqeyi sürətli, bir mövqeyi yavaş.
d) yavaş qayıt.
Orta düyünün göstəricisini qaytarır.

2 Adım: Ters əlaqəli siyahı funksiyasından istifadə edərək əlaqəli siyahının sol hissəsini geri çevirin.
ReverseLinkedlist (ortada)

3 Adım: tam əlaqəli siyahını və tərs sol hissəni götürən bir ispalindrome funksiyası yaradaraq əlaqəli siyahıların sol və sağ hissələrini müqayisə edin.

a) Sol hissə sağ hissə ilə eynidirsə, çap palindromdur
b) Başqa, palindrom deyil.

Alqoritm iş 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 reverseListIteratively(struct LL **head)
{
	struct LL *temp=NULL,*prev=NULL,*curr=*head;
	while(curr!=NULL)
	{
    temp=curr->next;
	curr->next=prev;
	prev=curr;
	curr=temp;
	}
  *head=prev;
	//O(number of nodes)
}

struct LL* middleOfList(struct LL**head)
{
	
	struct LL*slow=*head,*fast=*head;
	while(fast&&fast->next)
		{
			slow=slow->next;
			fast=fast->next->next;
		}
	return  slow;
	//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;
}

bool isPalin(struct LL *head, struct LL *middle)
{
	
	while(middle != NULL)
	{
		if(middle->data != head->data)
			return false;
		head = head->next;
		middle = middle->next;
	}
	
	return true;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,12);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,16); // uncomment to check and see that it is a palindrome
	insertAtBeginning(&head,12);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,23);
	
	cout<<"Given List is :-\n";
	display(&head);
	
	struct LL * middle = middleOfList(&head);
	reverseListIteratively(&middle);
	
	if(isPalin(head,middle))
		cout<<"\nGiven list is a palindrome\n";
	
	else
		cout<<"\nGiven list is not a palindrome \n";
	
	return 0;
}

Şərh yaz

Translate »