首页 > 代码库 > 单链表的环入口,环大小,解环
单链表的环入口,环大小,解环
1.单链表是否有环
使用快慢指针,都从head出发,慢指针一次一步,快指针一次两步,如果两个指针相遇,说明链表有环,否则,快指针为null或其next为null,到达末尾节点
function hasCircle(head){ var slow = head, fast = head; while(fast && fast.next){ slow = slow.next; fast = fast.next.next; if(slow == fast){ break; } } return fast != null && fast.next != null; }
2.单链表环的入口点
使用快慢指针,先判断是否有环,若有环,则慢指针从head出发,快指针与其同样的速度运行,直到相遇的一点,即为环入口点。
function getCircleEntry(head){ var slow = head, fast = head; while(fast && fast.next){ slow = slow.next; fast = fast.next.next; if(slow == fast){ break; } } if(fast == null || fast.next == null){ return null; } slow = head; while(slow != fast){ slow = slow.next; fast = fast.next; } return fast; }
3. 单链表环的大小
指针绕环一圈,记录其走过的步数,即为环大小
function getCircleLen(head){ var entry = getCircleEntry(head), len = 0 if(entry){ var p = entry; while(p != entry){ len++; p = p.next; } } return len; }
4. 解开一个环
找到环入口点的后面一个节点,即环的末尾节点,将其next设置为null,断链,解环
function breakCircle(head){ var entry = getCircleEntry(head); if(entry){ var p = entry; while(p.next != entry){ p = p.next; } p.next = null; } }
单链表的环入口,环大小,解环
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。