你好,游客 登录 注册 搜索
背景:
阅读新闻

尾指针及其简单应用

[日期:2017-06-24] 来源:cnblogs.com/AsuraDong  作者:AsuraDong [字体: ]

尾指针及其简单应用

循环链表如果拿到最后结点,若没有尾指针(rear),那么需要O(n)的时间。如果有的话,只需要O(1)的时间。

如果有两个链表,需要将他们连接,拥有尾指针只需要O(1)的时间复杂度。

此时,判断循环链表是否为空的方法:rear是否等于rear->next。

一道题目:将两个线性表A(a1,a2,a3...)和B(b1,b2,b3...)连接成一个线性表。

思路:A的rear不再指向A的head,而是指向B的head->next;然后需要将B的head释放(一个链表只能有一个头结点);最后,将B的rear重新指向A的head。


简单实现:

Node * Connect(Node *a_rear,Node *b_rear){ //参数是两个尾指针 
    Node *p = a_rear->next;//p指向A的head
    
    a_rear->next = b_rear->next->next; //a->rear指向B的head->next 
    
    free(b_rear->next);
    
    b_rear->next = p;
    return b_rear; //返回新链表的尾指针 
}

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-06/145148.htm

linux
相关资讯       尾指针 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款