一、题目描述

二、算法步骤

本题稍微有点复杂，观察结果链表，是将最后一个节点插入第一个节点后面，将倒数第二个节点插入第二个节点后面，关键在于如何很方便的找到倒数的节点。这里我们不妨尝试这种思想：将链表从中间分割开，然后后半段链表逆序，接着将两个链表合并成一个链表，这样似乎可以。但是要注意题目的空间复杂度为O(1)，因此我们需要找到原链表的中间节点，然后将后半段链表逆序，最后进行插入操作。
寻找空间位置可以使用快慢指针法，p指针一次走一步，q指针一次走两步。
最终代码展示：

#include 
#include 
#include
using namespace std;
typedef int elementType;
typedef struct Node
{
    elementType data;
    struct Node* next;
}Node,LinkList;
const int N = 100;
int a[N];
Node* Init(LinkList* L)
{
    L = (LinkList*)malloc(sizeof(Node));
    L->data = 0;
    L->next = NULL;
    return L;
}
Node* Create(int x)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}
void Print(LinkList* L)
{
    Node* cur = L;
    cur = cur->next;
    while (cur!= NULL)
    {
        cout << cur->data;
        if(cur->next!=NULL)printf("->");
        cur = cur->next;
    }
    printf("\n");
}

void Print2(LinkList* L)
{
    Node* cur = L;
    while (cur != NULL)
    {
        cout << cur->data;
        if (cur->next != NULL)printf("->");
        cur = cur->next;
    }
    printf("\n");
}
int main()
{
    /// 

    ///链表初始化
    /// 
    /// 
    LinkList* L = NULL;
    L = Init(L);
    int n; cin >> n;
    Node* cur = L;
    for (int i = 0; i < n; i++)
    {
        elementType x; cin >> x;
        Node* newNode = Create(x);
        cur->next = newNode;
        cur = cur->next;
    }
    cout << "L1为" << endl; Print(L);
    /// 

    /// 解法步骤
    /// 
    /// 

    Node* p = L, * q = L;//两指针从头结点出发
    while (q ->next!= NULL)
    {
        p = p->next;
        q = q->next;
        if (q->next != NULL) { q = q->next; }//走两步需要看后面是否为空
    }
    //现在p是中间，cur是后半段第一个节点，接着将该链表逆序
    Node* prev = p;
    cur = p->next;
    while (cur)
    {
        Node* behind = cur->next;//保存后节点
        cur->next = prev; //指向前节点

        prev = cur;//前节点更新为当前节点
        cur = behind;//当前节点更新为后节点
    }
    p->next = NULL;

    //最后进行插入操作
    p = L->next;//前半段链表开始
    q = prev;//后半段链表开始

    while (p!=q&&q&&p)
    {
        Node* behind1 = p->next; //保存p后面的节点
        p->next = q; //p指向q节点

        Node* behind2 = q->next;//保存q后面的节点
        q->next = behind1; //q指向p后面的节点

        p = behind1;//p往后走
        q = behind2;//q往后走
    }
    Print(L);
    return 0;
}

结果展示：
```cpp
5 //n为奇数
1 2 3 4 5
L1为
1->2->3->4->5
结果为:1->5->2->4->3

6 //n为偶数
1 2 3 4 5 6
L1为
1->2->3->4->5->6
结果为:1->6->2->5->3->4

# 三、总结
  本题难度还是挺大的，在电脑是debug都花了快10分钟，感觉考场上一遍写AC难度不小，总之是我太菜了。