---

(1)
因为要时间上尽可能高效，所以用空间换时间。创建一个新的数组A，将L中的后半部分放进A中。再创建一个新的链表B，开始遍历链表L，插入链表B，再遍历数组A，插入链表B，然后循环，直到链表L和A的next指针指向NULL。

（2）

typedef struct node{

 int data;

struct node *next;

}NODE;

void AssignList(NODE,*next){

int i=0;

while（*next!=NULL）

{

if(i>=n/2)

{

A[i]=L->data;

i+=1;

}

else

{

i+=1;

}

for(j=0;j<=n/2;j++)

{}

}

(3)

本算法用了一个n/2大小的数组，空间复杂度是O(n/2)。遍历了一次线性表L，再遍历了数组A和L表的前半部分所以时间为n/2+n/2。所以时间复杂度是O（n）.

---