题目解析：

【考】双指针算法，逆置法，归并法。

解析：因为题目要求空间复杂度为O(1)，即不能再开辟一条链表，因此我们只能用变量来整体挪动原链表。

第一步先找出中间节点

typedef NODE* Node;
Node find_mid(Node& h)
{Node pre, cur;pre = h->next;cur = pre;while (cur){cur = cur->next;if (!cur) break;cur = cur->next;if (!cur) break;pre = pre->next;}Node l2 = (Node)malloc(sizeof(NODE));l2->next = pre->next;pre->next = NULL;return l2;
}

第二步：把找出的中间节点之后的组成的新链表原地逆置

void reverse_list(Node& l)
{Node s, r, t;s = l->next, r = s->next, t = r->next;s->next = NULL;while (t){r->next = s;s = r;r = t;t = t->next;}r->next = s;l->next = r;
}

第三步：合并链表

void merge_list(Node& l1, Node& l2)
{Node a =  l1->next, b = l2->next;Node acur = a;a = a->next;while (a && b){acur->next = b;b = b->next;acur = acur->next;acur->next = a;a = a->next;acur = acur->next;}if(!a) acur->next = b;}

【注】以上三步核心算法即为笔试时写的答案

为了让读者看清正确性，我写出完整能运行的代码供参考

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode {ElemType data;struct LNode* next;
}NODE;
typedef NODE* Node;void insert_head_list(Node& l)
{ElemType data = 0;scanf("%d", &data);while (data != 9999){Node tmp = (Node)malloc(sizeof(NODE));tmp->data = data;tmp->next = l->next;l->next = tmp;scanf("%d", &data);}
}void print_list(Node& l)
{Node cur = l->next;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}Node find_mid(Node& h)
{Node pre, cur;pre = h->next;cur = pre;while (cur){cur = cur->next;if (!cur) break;cur = cur->next;if (!cur) break;pre = pre->next;}Node l2 = (Node)malloc(sizeof(NODE));l2->next = pre->next;pre->next = NULL;return l2;
}
void reverse_list(Node& l)
{Node s, r, t;s = l->next, r = s->next, t = r->next;s->next = NULL;while (t){r->next = s;s = r;r = t;t = t->next;}r->next = s;l->next = r;
}void merge_list(Node& l1, Node& l2)
{Node a =  l1->next, b = l2->next;Node acur = a;a = a->next;while (a && b){acur->next = b;b = b->next;acur = acur->next;acur->next = a;a = a->next;acur = acur->next;}if(!a) acur->next = b;}
int main()
{Node l = (Node)malloc(sizeof(NODE)); //存储头节点的头指针l->next = NULL;insert_head_list(l);//头插法print_list(l);Node l2 = find_mid(l);/*print_list(l);*/print_list(l2);reverse_list(l2);print_list(l2);merge_list(l, l2);print_list(l);return 0;
}

运行结果图片

链表长度为奇数时

链表长度为偶数时