重排链表空间复杂度O(1)

1. 找到链表中间位置指针

2. 翻转后一半链表

3. 将后一半链表依次取出一个节点按顺序插入前一半链表的对应位置

class Solution {
public:
    void reverse(ListNode *&head)  //翻转单链表
    {
        if(head&&head->next)
        {
            ListNode *p=head;
            ListNode *pn=head->next;
            p->next=NULL;
            while(pn)
            {
                ListNode *temp=pn->next;
                pn->next=p;
                p=pn;
                pn=temp;
            }
            head=p;
        }
    }
    
    //空间复杂的O(1)
    void reorderList(ListNode *head) {
        if(head&&head->next&&head->next->next)//超过三个节点才需要操作
        {
            //获取中间位置节点指针及其前驱指针indm和indm_pre
            ListNode *indl=head;
            int l=0;
            while(indl)
            {
                ++l;
                indl=indl->next;
            }
            int i=1,m=(l+1)/2;
            ListNode *indm=head->next;
            ListNode *indm_pre=head;
            while(i!=m)
            {
                ++i;
                indm=indm->next;
                indm_pre=indm_pre->next;
            }
            //翻转中间位置往后的链表
            reverse(indm_pre->next);
            //恢复中间位置指针
            indm=indm_pre->next;
            //将后半链表按顺序删除节点后插入前半链表
            ListNode *hp=head,*p=indm,*pr=indm_pre;
            while(p)
            {
                if(hp->next==p)
                    break;
                pr->next=p->next;
                p->next=hp->next;
                hp->next=p;
                hp=p->next;
                p=pr->next;
            }
        }
    }
};