文理学院程序设计在线练习


02-线性表 拆分单链表

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 732   Accepted Submission(s): 550
Problem Description

输入若干个绝对值不超过100的整数,建立单链表A,设计算法将单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A的元素类型为整型,要求B、C表利用A表的结点,不另外占用其它的存储空间,若采用带头结点的单链表实现则允许再申请一个头结点)。然后分两行按原数据顺序输出链表B和C。测试数据保证每个结果链表至少存在一个元素。

Input

首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据在一行上输入数据个数n及n个不含整数0且绝对值不超过100的整数。

Output

对于每组测试,分两行按原数据顺序输出链表B和C,每行的每两个数据之间留一个空格。

Sample Input
1
10 49 53 -26 79 -69 -69 18 -96 -11 68
Sample Output
-26 -69 -69 -96 -11
49 53 79 18 68