【数据结构】之循环链表

将单链表中终端节点的指针端由空指针改为指向头结点,形成一个环,这种头尾相接的单链表成为(单)循环链表。

循环链表不一定要有头结点。

循环链表与单链表的主要差异:在判断空链表的条件上:原来判断head.next()是否为null;现在需要判断reat.next是否等于rear。

循环链表不是用头指针,而是用尾(rear)指针来表示循环链表。

两个单循环链表的链接:

①断开A链表中尾指针指向头指针的环

②令A链表的的尾指针指向B链表的第一个结点

③将B链表的头结点释放

④令B链表的尾指针指向A链表的头结点。

  • 判断单链表中是否有环:链表的尾结点指向了链表中的某个结点。

方法一:

使用两个指针,p和q,p每次都往前走一步,而q每次都从头开始走到p所在的位置。如果不存在环,则p累计走的步数和q当次走的步数应该是一样的。如果不一样了,出现p步数大于q步数的情况,则存在环。

方法二:

快慢指针:使用p/q两个指针,p每次向前走一步,q每次向前走两步,若在某个时刻p==q,则存在环。

此条目发表在数据结构与算法分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注