美文网首页
数据结构学习

数据结构学习

作者: 陈果123 | 来源:发表于2017-05-14 17:06 被阅读4次

    无环单链表的反转

    http://blog.csdn.net/feliciafay/article/details/6841115
    超经典

    方法一:新创建一个单链表

    • 优点:此方法很简单,利用单链表的头插法即可
    • 缺点:多创建了一张表耗费内存空间
      -实现关键:遍历原链表,创建新链表,新链表使用头插法进行创建
    具体代码:
    LinkList p = (LinkList)malloc(sizeof(node));
    p->next = nill;
    while(p1){//原链表的只一个节点
    //创建一个新节点
    LinkList q = (LinkList)malloc(sizeof(node));
    q->data = p1->data;
    //头插法直接实现链表的反转
    q->next = p->next;
    p->next = q;
    p1 = p1->next;
    }
    

    方法二:循环顺序反转

    • 优点:不用开辟新的空间,只需要3个指针变量就行
    • 缺点:实现较复杂
    • 实现关键:这种也是一种遍历的反转方式,主要是要一个用于循环的指针p,以及一个指针q,用于表示p的前一个节点,另外还需要一个指针用于存储p的下一个节点
    实现代码
    LinkList p = head->next->next;
    LinkList  q = head->next;
    LinkList  r;
    while(p){
            //利用中间指针变量对指针p的下一个节点的位置进行存储
            r = p->next;
            p->next = q;
            q = p;
            p = r;
    }
    head = q;
    
    image.png

    方法三:同样是循环遍历的一种反转方式

    • 优点:优点在于这种实现的方式更加的省指针,不需要中间的指针,将头指针作为中转指针
    • 缺点:逻辑更复杂
    • 实现关键: 实现的关键在于换掉节点间的逻辑关系
    实现代码
    Linklist p = head->next;
    Linklist q;
    while(p->next != null){
      q = p->next;
      p->next = q->next;
      q->next = head->next;
      head->next = q;
    }
    //当p后没有节点时,将原来的头节点链接过来
    p->next = head;
    head = p->next->next;
    p->next->next = null;
    

    方法四: 递归实现

    • 优点:想法简单
    • 缺点:递归的通病就在于耗费内存空间,每递归一次操作系统都将把当前的上下文压栈,因此递归的次数越多耗费的内存将越多
    • 实现关键: 实现的关键在将问题进行划分,将大问题划分为多个子问题,但递归存在很多重复子问题,这也是为什么递归耗时的原因。递归的结束条件就是最后一个节点一经被反转
    LinkList revers(LinkList head,LinkList & new_head){
      if(head = null){
        return;      
      }
      if(head->next = null){
      new_head = head;  
      return head;
      }
     LinkList new_Tail = LinkList revers(head->next , new_head);
     //完成反向操作
     new_Tail ->next = head;
      //断开连接
     head->next = null;
    //返回当前的指针节点
     return head;
    }  
    

    总结

    •  感觉这些方法真是太牛逼了,都很精妙,各种实现方式也是很牛逼。最后一种递归的方法也是很赞。保存着每一次调用的地址,在递归进行回溯的时候再使用。牛逼。
      

    相关文章

      网友评论

          本文标题:数据结构学习

          本文链接:https://www.haomeiwen.com/subject/nmvqxxtx.html