有环链表查找环 博客分类: java数据结构&算法 java数据结构算法环状链表linkedlist
程序员文章站
2024-02-24 21:08:46
...
有环链表如何高效的判断是否有环,以及在何处产生环?
采用2个指针不同步数(步数小的每次1步,步数大的每次2步),步数大的如果能够与步数小的相遇则必然存在环。
相遇后的情况如图,假设相遇后步数大的回绕环遍历了n遍,步数小的肯定一遍也没遍历完,假设第一段距离为a,第2段距离为c,第3段距离为b
则有(a+c)*2 = a+n(b+c)+c,转换后得 a = n(b+c) - c,也就是说,从出发点出发,移动a的距离,刚好等于相遇点出发移动n个整圈减c的距离,这个点刚好就是环产生的点,由此可以设置2个指针,分别从根节点与相遇点出发,第一次相遇的地方则是环产生的点。
完成证明后,代码较为简单,如下
package com.xhb.algorithms; public class MyLinkedList { private LinkListNode<Integer> root = new LinkListNode<Integer>(null, null); private int length; private int point; /** * @param args */ public static void main(String[] args) { MyLinkedList list = new MyLinkedList(10045, 232); System.out.println(list.isHasRound()); System.out.println("the point cut obj is " + list.getCutPoint()); } /** * 初始化一个环链表 */ private MyLinkedList(int length, int point) { this.length = length; this.point = point; LinkListNode<Integer> current = this.root; for (int i = 1; i <= this.length - 1; i++) { current = current.next(new LinkListNode<Integer>(new Integer(i), null)); } if (this.point < 0) { current.next(null); } else { LinkListNode<Integer> pointObj = this.root; for (int i = 0; i < point; i++) { pointObj = pointObj.next(); } current.next(pointObj); } } public Integer getCutPoint() { LinkListNode<Integer> seekPoint = this.getSeekPoint(); System.out.println(seekPoint.data()); LinkListNode<Integer> a = this.root; while (true) { a = a.next(); seekPoint = seekPoint.next(); if (a == seekPoint) { return a.data(); } // System.out.println(a.data() +"," + seekPoint.data()); } } private LinkListNode<Integer> getSeekPoint() { LinkListNode<Integer> a = this.root; LinkListNode<Integer> b = this.root; a = a.next(); b = b.next().next(); while (true) { a = a.next(); b = b.next(); if (b == null) { return null; } if (a == b && b != null) { return b; } b = b.next(); if (b == null) { return null; } if (a == b && b != null) { return b; } } } public boolean isHasRound() { return this.getSeekPoint() != null; } } class LinkListNode<T> { private LinkListNode<T> next = null; private T data; public LinkListNode(T data, LinkListNode<T> next) { this.data = data; this.next = next; } public LinkListNode<T> next() { return next; } public LinkListNode<T> next(LinkListNode<T> next) { this.next = next; return next; } public T data() { return this.data; } @Override public String toString() { return data.toString(); } }