/*
设计一个算法，将带头结点的单链表A分解成两个结构相同的单链表B和C
使得B中的元素是A中大于等于0的元素，C中的元素是A中小于0的元素。
要求存储空间仍使用A的存储空间。 
*/

#include<stdio.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

/*
初始化单链表 
*/
int InitList(LinkList &L){
	L=new LNode;
	L->next=NULL;
	return 1;
}

//创建链表 
void CreateList(LinkList &L,int n){
	L=new LNode;
	L->next=NULL;
	for(int i=0;i<n;i++){
		printf("请输入第%d个元素的值:",i+1);
		struct LNode *p;
		p=new LNode;
		scanf("%d",&p->data);
		p->next=L->next;
		L->next=p;
	}
}

//遍历 
void TraveList(LinkList L){
	struct LNode *p;
	p=L->next;
	while(p){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

void CutList(LinkList &A,LinkList &B,LinkList &C){
	struct LNode *pa,*pb,*pc;
	pa=A->next;
	//B=C=A;
	B=new LNode;
	C=new LNode;
	B->next=NULL;
	C->next=NULL;
	pb=B;
	pc=C;
	while(pa){
		if(pa->data>=0){
			pb->next=pa;
			pa=pa->next;
			pb=pb->next;
			pb->next=NULL;//这一句不能少 
		}else if(pa->data<0){
			pc->next=pa;
			pa=pa->next;
			pc=pc->next;
			pc->next=NULL;//不能少 
		}
	} 
}

int main(){
	LinkList A,B,C;
	
	if(InitList(A)){
		printf("链表A初始化成功!\n");
	}else{
		printf("链表A初始化失败!\n");
	}
	
	if(InitList(B)){
		printf("链表B初始化成功!\n");
	}else{
		printf("链表B初始化失败!\n");
	}
	
	if(InitList(C)){
		printf("链表C初始化成功!\n");
	}else{
		printf("链表C初始化失败!\n");
	}
	
	printf("请输入链表A的长度:");
	int n1;
	scanf("%d",&n1);
	CreateList(A,n1);
	printf("链表A的结构如下:\n");
	TraveList(A);
	
	CutList(A,C);
	
	printf("B链表的结构如下:\n");
	TraveList(B);
	
	printf("C链表的结构如下:\n");
	TraveList(C);
	
	return 0; 
}