将单链表中终端节点的指针端由空指针改为指向头结点,形成一个环,这种头尾相接的单链表成为(单)循环链表。
循环链表不一定要有头结点。
循环链表与单链表的主要差异:在判断空链表的条件上:原来判断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,则存在环。