---

（1）输出链表可以视作为链表的前半段，与逆置的链表后半段进行逐个合并的结果，所以将链表后半段进行你只，设置pq两指针，p走一步，q走两步，q到末尾时，p刚好在链表中间，设前半段头节点为head1，后半段为head2,合并时的链表为head3，利用head3将head1与head2依次合并即可

(2) 
NODE head1;

head1= (node*)malloc(sizeof(NODE))

node* p=head1;

node*q=head1;

node* head2=head3=NULL;
While(q->next)
{

p=p->next;

q=q->next->next;
}

head2=p;

beg=p->next;end=p->next->next;
while(end)//后半段链表逆置
{
beg->next=end->next;

end->next=head2->next;

head2->next=end;

end=beg->next;
}

node* p3=head3;
While(head2)//合并链表
{
  p3->next=head1->next;

head1=head1->next;
p3=p3->next;

p3->next=head2->next;

head2=head2->next;

p3=p3->next;
}
(3)查询p指针时间复杂度为O(n),逆置为O(n),合并为O(n),总共时间复杂度为O(n)

---