## 問題描述 > 設C={a1,b1,a2,b2,...,an,bn}為線性表，采用帶頭結點的hc單鏈表存放，設計一個就地算法，將其拆分為兩個線性表，使得A={a1,a2,a3,...an}，B={bn,...,b2,b1}。 ## 算法思想 > 本題實際上跟[ 第1章第2節練習題8 奇偶拆分單鏈表 ](http://blog.csdn.net/u013595419/article/details/50497867)大同小異。 因為本題中原來的單鏈表基本遞增有序，因此采用尾插法創建單鏈表可以避免創建的鏈表與邏輯順序相反的問題，然后將序號為偶數的結點摘下，然后通過頭插法創建單鏈表的方式星馳單鏈表B，這樣以來便就形成了正序的序列A和逆序的序列B。 ## 算法描述 ~~~ LinkList SeparateList(LNode* head){ LNode *hb; hb=(LNode*)malloc(sizeof(LNode)); LNode *pre=head; LNode *p=head->next; while(p){ if(p->num%2==0){ pre->next=p->next; p->next=hb->next; hb->next=p; p=pre->next; }else{ pre=p; p=p->next; } } return hb; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ int num; ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList SeparateList(LNode*); int LengthList(LNode*); void Print(LNode*); int main(int argc,char *argv[]) { LNode *hc; hc=(LNode*)malloc(sizeof(LNode)); hc->next=NULL; hc->num=0; hc=CreatList(hc); Print(hc); LNode *ha; LNode *hb; hb=SeparateList(hc); ha=hc; Print(ha); Print(hb); } //尾插法建立單鏈表 LinkList CreatList(LNode* head) { LNode *r=head; LNode *L; ElemType x; int i=1; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->num=i++; L->data=x; r->next=L; r=L; scanf("%d",&x); } r->next=NULL; return head; } //分離單鏈表 LinkList SeparateList(LNode* head) { LNode *hb; hb=(LNode*)malloc(sizeof(LNode)); LNode *pre=head; LNode *p=head->next; while(p){ if(p->num%2==0){ pre->next=p->next; p->next=hb->next; hb->next=p; p=pre->next; }else{ pre=p; p=p->next; } } return hb; } //打印全部結點 void Print(LNode* head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~