【问题描述】

某非空单链表L中的所有元素为整数，设计一个算法将所有小于零的结点移到所有大于等于零的结点的前面。

【输入形式】

两行，第一行是整数个数，第二行是整数列表

【输出形式】

整数列表
【样例输入】

6

-1 2 3 -3 -5 6

【样例输出】

-5 -3 -1 2 3 6

【样例说明】

将小于0的整数插入到头部位置
【评分标准】

必须使用单链表

多写了一个排序的功能，就这样吧。

#include<iostream>
using namespace std;

struct node {
	int data;
	node* next;
};

node* create(int size) {
	node* head = new node; head->next = NULL;
	node* p = head; node* q = NULL;
	for (int i = 0; i < size; i++) {
		q = new node;
		cin >> q->data;
		q->next = NULL;
		p->next = q;
		p = q;
	}
	return head;
}

//排序,从小到大,n为链表长度
void sort(node* L,int n) {
	int z;
	for(int i=0;i<n;i++){
		node* p = L->next; node* q = p->next;
		while (q!= NULL) {
			if (p->data > q->data) {
				z = p->data;
				p->data = q->data;
				q->data = z;
			}
			p = p->next;
			q = q->next;
		}
	}
}

//将负数平移到正数左边
void sort2(node* L,int n) {
	//L1存放负数
	node* L1 = new node; L1->next = NULL;
	//L2存放正数
	node* L2 = new node; L2->next = NULL; node* y = L2;
	node* p = L->next;
	//临时节点
	node* q = NULL;
	//拆分
	while (p != NULL) {
		if (p->data < 0) {
			q = new node;
			q->data = p->data;
			q->next = L1->next;
			L1->next = q;
		}
		else {
			q = new node;
			q->data = p->data;
			q->next = NULL;
			y->next = q;
			y = q;
		}
		p = p->next;
	}
	//合并
	p = L->next;
	node* x2 = L1->next;
	node* y2 = L2->next;
	for (int i = 0; i < n; i++) {
		if (x2 != NULL) {
			if (p) {
				p->data = x2->data;
				x2 = x2->next;
				p = p->next;
			}
		}
		else {
			if (p) {
				p->data = y2->data;
				y2 = y2->next;
				p = p->next;
			}
		}
	}

}

//遍历
void print(node* L) {
	node* p = L->next;
	while (p != NULL) {
		cout << p->data<<" ";
		p = p->next;
	}
}

int main() {
	node* L;
	int n;
	cin >> n;
	L = create(n);
	sort2(L,n);
	cout << endl;
	print(L);
}