首页  >  文章  >  数据库  >  CCI 2.6 寻找有环链表环路的开头节点

CCI 2.6 寻找有环链表环路的开头节点

WBOY
WBOY原创
2016-06-07 15:43:001167浏览

给定一个有环链表,实现以算法返回环路的开头结点。 有环链表的定义 在链表中某个节点的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;
	}
}


声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn