算法1

思路：
从链表前面取一个元素，再从链表最后取一个元素，考察的是链表的合并与反转
什么意思呢？就是链表变成两半，前半部分[n/2],后半部分n-[n/2],得到的后半部分进行反转，得到的序列
就是n,n-1,n-2…,然后从前半个链表取一个元素，后半个反转后的链表中取一个元素，进行链表合并
总共分为三步：
1；求长度
2：得到中间两个点的位置，让a为左半段最后一个节点，b为右半段第一个节点，c为右半段第二个节点，形成两个链表，在这里对右半段节点进行链表反转
3：两个新形成的链表进行合并

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */


class Solution {
public:
    void rearrangedList(ListNode* head) {
        if(!head->next)return ;//如果只有一个节点，直接返回

        int n=0;//这部分是求前半段的长度，用与获得链表中间的两个点
        for(auto p=head;p;p=p->next)n++;
        int left=(n+1)/2;

        auto a=head;//形成左半部分的链表1
        for(int i=0;i<left-1;i++)a=a->next;

        auto b=a->next,c=b->next;//b,c是右半部分的第一个节点，和第二个节点
        a->next=b->next=NULL;

        while(c)//进行后半段的反转
        {
            auto p=c->next;
            c->next=b;
            b=c,c=p;

        }
        for(auto p=head,q=b;q;)//链表合并
        {
            auto o=q->next;
            q->next=p->next;
            p->next=q;
            p=p->next->next;
            q=o;
        }

    }
};