单链表的拆分（不创建新的链表）

分数 5

作者 李卫明

单位 杭州电子科技大学

1.4 编写程序，输入若干正整数，按从小到大次序建立1个带头结点单链表，设计一个实现单链表分离算法的Split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点，最后显示2个单链表，在程序退出前销毁单链表。要求Split算法时间复杂性达到O（n）,程序不可存在内存泄漏。

输入格式:

若干正整数。

输出格式:

每个单链表输出占一行，元素间用分隔符->分隔；初始单链表、剩余元素单链表、偶数元素单链表，共3行。

输入样例:

100 2 3  50 2 1 5 8

输出样例:

1->2->2->3->5->8->50->100
1->3->5
2->2->8->50->100

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

C程序如下：

#include<stdio.h>  
#include<stdlib.h>  typedef struct LinkList {  int Data;  struct LinkList *Next;  
} LinkList, *List;  List  CreatHead();
void Display(List L);
List Destroy(List L);
void Reverse(List L);int main() {List firstHead, firstTail, secondHead, secondTail, thirdHead, thirdTail;firstHead = CreatHead();firstTail = firstHead;secondHead = CreatHead();secondTail = secondHead;thirdHead = CreatHead();thirdTail = thirdHead;int v;while (scanf("%d", &v) != EOF) {List new = CreatHead();new->Data = v;firstTail->Next = new;firstTail = new;}Sort(firstHead);Display(firstHead);while (firstHead->Next != NULL) {//拆分为两个链表并且不创建新的结点if (firstHead->Next->Data % 2 == 0) {List p = firstHead->Next;//记录要拆分的数据地址firstHead->Next = p->Next;//让原来链表中待拆分数据的前后链接起来p->Next = NULL;//待拆分结点的Next域赋值为空thirdTail->Next = p;//尾插法插入新的链表thirdTail = p;}else {List p = firstHead->Next;firstHead->Next = p->Next;p->Next = NULL;secondTail->Next = p;secondTail = p;}}/*while (firstHead->Next != NULL) {firstHead = firstHead->Next;if (firstHead->Data % 2 == 0) {List new = CreatHead();new->Data = firstHead->Data;thirdTail->Next = new;thirdTail = new;}else {List new = CreatHead();new->Data = firstHead->Data;secondTail->Next = new;secondTail = new;}}*/Display(secondHead);Display(thirdHead);Destroy(firstHead);Destroy(secondHead);Destroy(thirdHead);
}List CreatHead() {List p = (List)malloc(sizeof(LinkList));p->Next = NULL;return p;
}void Display(List L) {L = L->Next;while (L) {printf("%d", L->Data);L = L->Next;if (L != NULL)printf("->");}printf("\n");
}List Destroy(List L) {List p = L->Next;while (p) {L->Next = p->Next;free(p);p = L->Next;}free(L);return L = NULL;
}void Sort(List L) {List pStar, pCur;pStar = L->Next;for (;pStar != NULL;pStar = pStar->Next) {List pMin = pStar;for (pCur = pMin->Next;pCur != NULL;pCur = pCur->Next) {if (pCur->Data < pMin->Data) {pMin = pCur;}}if (pMin != pStar) {int temp = pMin->Data;pMin->Data = pStar->Data;pStar->Data = temp;}}
}