链表中奇偶结点的移动

本题要求实现一个函数，实现对单循环链表中奇数和偶数结点的移动，要求奇数在前面，偶数在后面，且结点之间的相对顺序不变。 1.建立结构体并宏定义变量。代码如下

LinkList CreateList_Tail_loop() { LinkList head = (LinkList)malloc(sizeof(struct Node)); PNode cur = NULL; PNode tail = head; DataType data; scanf("%d", &data); while (data != -1) { cur = (struct Node*)malloc(sizeof(struct Node)); cur->data = data; tail->next = cur; tail = cur; scanf("%d", &data); } tail->next = head; return tail; }

2.奇偶点移动函数，此函数是本题的重点，采用的方法大致为： ①建立两个新链表，head1链表负责装偶数，head2链表负责装奇数。 ②遍历链表每一个节点，若为奇数，则利用尾插法插入head2链表；若为偶数，则利用尾插法插入head1链表； ③将head1和head2的链表头尾连接，形成一个新的单向循环链表，并将次链表的尾指针作为返回值。 代码如下

PNode Move_Odd_Even(LinkList tail) { PNode head=tail->next,pre=head->next,q=pre->next; free(head);//释放原链表的头指针，因为头指针无数据 LinkList head1=(LinkList)malloc(sizeof(struct Node)); PNode pre1=head1;//pre1指针随着新插入的节点移动，便于进行尾插法 LinkList head2=(LinkList)malloc(sizeof(struct Node)); PNode pre2=head2;//pre2指针随着新插入的节点移动，便于进行尾插法 while(q!=head->next)//原链表是循环链表，当q遍历到原来pre的位置时,遍历结束 { if(pre->data%2==0)//判断元素是否为偶数 { pre->next=pre1->next; pre1->next=pre; pre1=pre1->next; } else//若不是偶数，则为奇数 { pre->next=pre2->next; pre2->next=pre; pre2=pre2->next; } pre=q; q=q->next;//pre始终保持在q的前面 } head1=head1->next;//******** pre2->next=head1;//******* pre1->next=head2;//**星号部分的语句均为将0head1链表和head2链表进行形成一个新的但循坏链表 return pre1;//返回新循坏链表的尾指针 }

3.打印链表函数。注意，该函数的形参为单循环链表的尾指针，代码如下

void print(LinkList tail) { PNode head = tail->next; PNode p = head->next; while (p != head) { printf("%d ", p->data); p = p->next; } }

4.释放链表，防止占用内存，注意，此函数的形参也是尾指针 代码如下

void DestoryList_Link(LinkList tail) { PNode pre = tail->next; PNode p = pre->next; while (p != tail) { free(pre); pre = p; p = pre->next; } free(pre); free(tail); }

5.主函数如下

int main() { LinkList tail = NULL; LinkList p = NULL; tail = CreateList_Tail_loop(); p = Move_Odd_Even(tail); print(p); DestoryList_Link(tail); return 0; }

输入和输出样例如下，此编译环境为Code::Block17.12