求有环链表的环起点
给定一个有环链表 实现一个算法 返回环路的开头结点
有环链表的定义:
在链表中某个节点的next的元素指向在它前面出现过的节点,则表明该链表存在环路
import java.util.HashSet;
/*
* 给定一个有环链表 实现一个算法 返回环路的开头结点
*
* 有环链表的定义:
* 在链表中某个节点的next的元素指向在它前面出现过的节点,则表明该链表存在环路
*
*/
public class _2_6CircleLinkedList {
//返回环的起点 第一种方法
public ListNode check(ListNode head)
{
ListNode p = head;
HashSet set = new HashSet();
while(true)
{
if(set.contains(p))
{
return p; //若果set里面包含p的话 说明前面就出现过这个节点,那么p就是环路链表的开始节点
}else
{
set.add(p);
p = p.next;
}
}
}
//判断链表是否有环
//用两个指针 一个指针 一次走一步 另一个一次走两步 如果相遇的话说明有环
public static boolean hasCircle(ListNode head)
{
ListNode s = head;
ListNode f = head;
while(true)
{
s = s.next;
f = f.next.next;
if(s == f)
{
return true;
}
if(f.next == null || f.next.next==null)
{
return false;
}
}
}
//返回环的起点 第二种方法
public static ListNode beginOfCircle(ListNode head)
{
ListNode s = head;
ListNode f = head;
while(true)
{
s = s.next;
f = f.next.next;
if(s == f)
{
break;
}
}
ListNode p = head;
while(p!=s)
{
p = p.next;
s = s.next;
}
return p;
}
public static void main(String[] args) {
ListNode node = new ListNode(1);
node.next = new ListNode(2);
node.next.next = new ListNode(32);
node.next.next.next= new ListNode(32);
node.next.next.next.next = new ListNode(2);
node.next.next.next.next.next = new ListNode(2);
node.next.next.next.next.next.next = node.next;
_2_6CircleLinkedList obj = new _2_6CircleLinkedList();
ListNode res = obj.check(node);
//System.out.println(res.data);
System.out.println(obj.beginOfCircle(node).data);
//System.out.println(obj.hasCircle(node));
}
}