Code:
#include <stdio.h>#include <stdlib.h>
struct Node
{
int data;
struct Node* prev;
struct Node* next;
};
void addDLL(struct Node** head, struct Node** tail, int temp)
{
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data=temp;
newNode->prev=NULL;
newNode->next=NULL;
if (*head==NULL && *tail==NULL)
{
*head=newNode;
*tail=newNode;
}
else
{
newNode->prev=*tail;
newNode->prev->next=newNode;
*tail=newNode;
}
//printf("data %d,newnode add %p, next %p, prev %p\n", newNode->data, newNode, newNode->next, newNode->prev);
}
void deleteDLL(struct Node** max)
{
//printf("deleting this data=%d ptr=%p\n",(*max)->data, *max);
if ((*max)->prev!=NULL && (*max)->next!=NULL)
{
(*max)->prev->next=(*max)->next;
(*max)->next->prev=(*max)->prev;
//printf("linking of max prev next with max next done maxprenext data %d, maxprenext ptr %p, maxnext data %d, maxnext ptr %p\n", (*max)->prev->data, (*max)->prev, (*max)->next->data, (*max)->next);
//printf("linking of max next prev with max prev done maxnextprev data %d, maxnextprev ptr %p, maxprev data %d, maxprev ptr %p\n", (*max)->next->data, (*max)->next, (*max)->prev->data, (*max)->prev);
}
else if ((*max)->prev==NULL && (*max)->next!=NULL)
{
(*max)->next->prev=NULL;
//printf("null linko");
}
else if ((*max)->prev!=NULL && (*max)->next==NULL)
{
(*max)->prev->next=NULL;
//printf("null linko");
}
free(*max);
//printf("deleted\n");
}
void printDLL(struct Node* head)
{
while (head!=NULL)
{
printf("%d->",head->data);
head=head->next;
}
printf("\n");
}
void findMax(struct Node* head, struct Node** max, int n)
{
while (head!=NULL)
{
if (head->data==n)
{
*max=head;
break;
}
else
{
head=head->next;
}
}
}
void solve(struct Node** max, int n)
{
int result=0;
if ((*max)->prev==NULL)
{
//printf("first no. max\n");
while ((*max)->next!=NULL)
{
if ((*max)->data-(*max)->next->data!=1)
{
result=1;
break;
}
else
{
*max=(*max)->next;
}
}
}
else if ((*max)->next==NULL)
{
//printf("last no. max\n");
while ((*max)->prev!=NULL)
{
if ((*max)->data-(*max)->prev->data!=1)
{
result=1;
break;
}
else
{
*max=(*max)->prev;
}
}
}
else
{
n--;
//printf("mid no. max\n");
while (1)
{
if ((*max)->prev!=NULL && (*max)->data-(*max)->prev->data==1)
{
n--;
if (n==0) break;
//printf("N=%d prev max data=%d max ptr=%p prev data=%d prev ptr=%p\n", n, (*max)->data, *max, (*max)->prev->data, (*max)->prev);
struct Node* temp = (*max)->prev;
deleteDLL(max);
*max=temp;
}
else if ((*max)->next!=NULL && (*max)->data-(*max)->next->data==1)
{
n--;
if (n==0) break;
//printf("N=%d next max data=%d max ptr=%p next data=%d next ptr=%p\n",n, (*max)->data, *max, (*max)->next->data, (*max)->next);
struct Node* temp = (*max)->next;
deleteDLL(max);
*max=temp;
}
else
{
result=1;
break;
}
}
}
if (result==0)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
int main()
{
int i,n;
scanf("%d", &n);
struct Node* head=NULL;
struct Node* tail=NULL;
struct Node* max=NULL;
for (i=0; i<n; i++)
{
int temp;
scanf("%d",&temp);
addDLL(&head, &tail, temp);
}
findMax(head, &max, n);
solve(&max, n);
//printDLL(head);
return 0;
}
Thanks to all again!