首页 > 编程语言 > 详细

408 2019算法题目

时间:2019-10-19 20:55:52      阅读:218      评论:0      收藏:0      [点我收藏+]

算法基本思想:分三步完成:

第一步:采用两个指针交替前行,找到单链表中间节点

第二步:将单链表后半段节点原地逆置

第三步:从单链表前后两段各取一个节点,按要求重排

代码实现:

void change_list(Node  *h)
{
    Node *p,*q,*r,*s;
    p=q=h;
    while(q->next!=null)//寻找中间节点
    {
        p=p->next;//p走一步
        q=q->next;
        if(q->next!=NULL)q=q->next;//q走两步
    }
    q=p->next//p所指即为中间节点,q为后半段链表首节点
    p->next=NULL;
    while(q!=NULL)
    {
        r=q->next;
        q->next=p->next;
        p->next=p;
        q=r;
    }//将链表后半段逆置
    s=h->next;//s指向前半段的第一个节点,即插入点
    q=p->next;//q指向后半段第一个节点
    p->next=NUll;
    while(q!=NULL)//将链表后半段节点插到指定位置
    {
        r=q->next;//r指向后半段的下一个节点
        q->next=s->next;//将q所指节点插入到s节点之后
        s->next=q;
        s=q->next;//s指向前半段下一个插入点
        q=r;
    }
}

    

  算法复杂度为O(N)

408 2019算法题目

原文:https://www.cnblogs.com/yangmenda/p/11705039.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!