39-17

设计一个算法用于判断带头结点的循环双链表是否对称

循环双链表！！

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *pre,*next;
}LNode,*LinkList;

void CreateList(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    L->pre=NULL;
    LNode *p=L;
    LNode *r;
    int x;
    scanf("%d",&x);
    while(x!=999)
    {
        LNode *node=(LNode*)malloc(sizeof(LNode));
        node->data=x;
        node->next=NULL;
        node->pre=p;
        p->next=node;
        p=node;
        scanf("%d",&x);
    }
    L->pre=p;                    //只需要将L->pre指向最后一个结点就可以了 
}

void displayList(LinkList L)
{
    LNode *p=L->next,*r=L->pre;
    while(p)
    {
        printf("%d  ",p->data);
        r=p;
        p=p->next;
    }
    printf("\n");
    
    while(r!=L)        //判断pre指针是否正确         //当r->L时，遍历完成 
    {
        printf("%d  ",r->data);
        r=r->pre; 
    }
}

void Judge(LinkList L)
{
    LNode *p=L->next,*r=L->pre;
    while(p->next!=r&&p->next!=r->pre)        //指针界限问题，好好分析 
    {
        if(p->data!=r->data)
        {
            printf("No");
            return; 
        }
        else
        {
            p=p->next;
            r=r->pre;
        }
    }
    printf("Yes");
} 

int main()
{
    LinkList L;
    CreateList(L);
    displayList(L);
    printf("\n");
    Judge(L);
    return 0;    
}