单链表逆置、重排

单链表逆置：
思想：逆置链表初始为空，表中结点从原链表中依次取出，再采用头插法逐个插入逆置链表的表头，使它成为逆置链表的首元结点，循环操作，直到原链表为空。

LinkList ReverseList( LinkList head )
{
    ListNode *p ,*q ; //设置两个临时指针变量
    if( head->next && head->next->next)
    {
        p=head->next;
        q=p->next;
        p -> next=NULL;
        while (q)
        {     p=q;
            q=q->next ;
            p->next = head-> next ;
            head->next = p;
        }

    }
    return head; 
}

复杂度：时间复杂度O(n); 空间复杂度O(1)

重排单链表

思想：找到单链表的中间结点，然后将后半部分逆置，逆置采用头插法，最后，把逆置的链表依次插入前半部分。

struct LNode *ReverseList( struct LNode *head )    //逆置单链表
{
    struct LNode *p ,*q ; //设置两个临时指针变量
    if( head->next && head->next->next)
    {
        p=head->next;
        q=p->next;
        p -> next=NULL;
        while (q)
        {     p=q;
            q=q->next ;
            p->next = head-> next ;
            head->next = p;
        }
    }
    return head; 
}


struct LNode *fun(struct LNode *L){
    struct LNode *p,*q,*r,*s;
    r=(struct LNode *)malloc(sizeof(struct LNode));
    p=L->next;
    q=p->next;
    while(q->next!=NULL){    //找到中间结点的下一个 
        if(q->next->next!=NULL){
            p=p->next;
            q=q->next->next;
        }else{
            
            q=q->next;
        }    
    }
    r->next=p->next->next;
    p->next->next=NULL;
    
    r=ReverseList(r);    //将后半部分逆置 
    s=L->next;
    q=s->next;
    p=r->next;
    while(p){    //逆置后的后半部分插入到前半部分 
        s->next=p;
        p=p->next;
        s->next->next=q;
        s=q;
        q=q->next;    
    }
    return L;
}