CCI2.6寻找有环链表环路的开头节点

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CCI2.6寻找有环链表环路的开头节点，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1485字，纯文字阅读大概需要3分钟。

内容图文

给定一个有环链表，实现以算法返回环路的开头结点。 有环链表的定义 在链表中某个节点的next元素指向它前面出现过的节点，则表明该链表存在环路。 示例 输入：A-B-C-D-E-C(C节点出现两次) 输出：C 分析 ： 1，快慢指针法判断链表是否有环 fast每次前移两步，

给定一个有环链表，实现以算法返回环路的开头结点。

有环链表的定义

在链表中某个节点的next元素指向它前面出现过的节点，则表明该链表存在环路。

示例

输入：A->B->C->D->E->C(C节点出现两次)

输出：C

分析：

1，快慢指针法判断链表是否有环

fast每次前移两步，slow每次前移一步，两指针若能相遇，则有环，否则没有环。

2，假设链表头到环头移动k步，slow指向环头的时候，fast移动了2*k步，此时两者相距k步，也可以认为快指针再过m*size-k步之后追上慢指针。当两者相遇的时候，则慢指针距离环头还有k步。因为此时不知道k的具体大小，但是知道k是链表头到环头的步数，让fast指向链表头，之后快慢指针每次往后移动一步，两者相遇的地方就是环头。

package test;

public class FindLoopStart {
	public Node findLoopStart(Node head){
		Node fast = head;
		Node slow = head;
		while(fast!=null || fast.next!=null){
			fast = fast.next.next;
			slow = slow.next;
			if(fast == slow)
				break;
		}
		//没有环则返回null
		if(fast==null || fast.next==null)
			return null;
		//相遇之后，slow节点再走k步达到环开头
		//此时，并不知道k的具体值，但是知道k是从链表开头到环头的步数
		//于是，让fast指向链表头，每次往后移一步，则再次相遇的时候，走的步数就是k
		//则相遇地点就是环的开头
		fast = head;
		while(fast != slow){
			fast = fast.next;
			slow = slow.next;
		}
		return slow;
	}
}

内容总结

以上是互联网集市为您收集整理的CCI2.6寻找有环链表环路的开头节点全部内容，希望文章能够帮你解决CCI2.6寻找有环链表环路的开头节点所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端