Question

设有一个带头结点的循环双链表L=(a1,a2,…,an-1,an)。设计一个时间复杂度为

设有一个带头结点的循环双链表L=(a1,a2,…,an-1,an)。设计一个时间复杂度为O(n)的算法，将L改造成L=(a1,a3,a5,…,an,…,a6,a4,a2)。

我的思路是首先建立原始链表head，再创建一个链表head1，将偶数位元素从原链表中删去，以头插法插入head1中，最后再连接head和head1.。但是现在输出有问题。。求解。。如果不能解决，可以提供一个代码给我吗？但是请注明思路和步骤含义。

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

typedef struct dulnode
{
int data;
struct dulnode *prior;
struct dulnode *next;
}dulnode;
#define LEN sizeof(dulnode)
dulnode *Create_dulnode();

void main()
{
dulnode *p,*q,*m,*head,*head1;
head=Create_dulnode();
p=head;
p=p->next;
head1=(dulnode*)malloc(LEN);
head1->next=NULL;
while(1)
{
m=p;
if((p->next->next!=head)&&(p->next!=head))
{
q=p->next;
p=p->next->next;
m->next=p;
p->prior=m;
q->next=head1->next;
if(head1->next!=NULL)
{
head1->next->prior=q;
}
head1->next=q;
q->prior=head1;
}
else if(p->next->next==head)
{
p->next->next=head->next;
head->next->prior=p->next;
q->next=head;
head->prior=q;
break;
}
else if(p->next==head)
{
p->next=head1->next;
p=head1->next->prior;
q->next=head;
head->prior=q;
break;
}
}
p=head;
p=p->next;
while(p->next!=NULL)
{
printf("%d",p->data);
p=p->next;
}
printf("%d",p->data);
p->next=head;
head->prior=p;
}

dulnode *Create_dulnode()
{//创建一个双向链表
dulnode *head,*p,*c;
int data;
head = (dulnode*)malloc(LEN);
p = head;
printf("请录入链表，输入0停止录入数据\n");
printf("请输入数据\n");
scanf("%d",&data);
while(data != 0)
{
c = (dulnode*)malloc(LEN);
c->data = data;
c->prior=p;
p->next = c;
p= c;
printf("请输入数据\n");
scanf("%d",&data);
}
p->next=head;
head->prior = p;//C链表建立完成
return head;
}

Answer 1

思路没有问题，应该可行
你这个循环链表确定是带头结点还是不带头结点？帮确认一下啊

追问

前面开辟了head和head1，，应该是带的吧。。

追答

双向循环链表带头结点处理起来真麻烦！  自己研究一下吧，只能自己去慢慢体会了，解释起来很繁琐
int main()
{
    dulnode *p,*q,*n,*m,*head,*head1;
    head=Create_dulnode();

    head1=(dulnode*)malloc(LEN);
    m=head1;
    n=head;
    p=head->next;
    while(p != head )
    {
        m->next=p ;
        p->prior=m ;
        m=p ;

        if ( p->next == head )
            break;
        q=p->next;
        p=q->next;
        q->next=n;
        n->prior = q;
        n=q;
    }
    m->next=head1;
    head1->prior=m;
    n->prior=head;
    head->next=n;

    head1->prior->next=head->next;
    head->next->prior=head1->prior;
    head->prior->next=head1;
    head1->prior=head->prior;
    p=head1->next;
    while(p!=head1)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return 0;
}