欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

有环链表查找环 博客分类: java数据结构&算法 java数据结构算法环状链表linkedlist 

程序员文章站 2024-02-24 20:12:22
...

有环链表如何高效的判断是否有环,以及在何处产生环?

采用2个指针不同步数(步数小的每次1步,步数大的每次2步),步数大的如果能够与步数小的相遇则必然存在环。

有环链表查找环
            
    
    博客分类: java数据结构&算法 java数据结构算法环状链表linkedlist 

 

相遇后的情况如图,假设相遇后步数大的回绕环遍历了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();
	}
}
  • 有环链表查找环
            
    
    博客分类: java数据结构&算法 java数据结构算法环状链表linkedlist 
  • 大小: 15.9 KB