package linkedlist;
public class ReverseListNew {
static class Node{
int val;
Node next;
Node(int item) {
this.val = item;
this.next = null;
}
}
/***
* 找出链表中环入口的位置，返回该位置的值，如果没有环返回-1
* 这里为了说明例子，假定节点的值都是正数，所以返回值用-1表示没环情况
* */
public static int checkLoop(Node head) {
if(head == null || head.next == null) {
return -1;
}
Node fast = head.next.next;
Node slow = head.next;
Node meet = null;
while (fast!=null && fast.next!=null) {
if(fast.val == slow.val) {
meet = fast;
break;
}
fast = fast.next.next;
slow = slow.next;
}
if(meet == null)
return -1;
while (head.val!= meet.val) {
head = head.next;
meet = meet.next;
}
return meet.val;
}
public static void main(String[] args) {
Node node = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node1; ///node1是环的入口，所以函数返回1
node4.next = node5;
System.out.println(checkLoop(node));
}
}
链表——链表中环的检测
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 链表中环的入口结点 题目描述 一个链表中包含环，请找出该链表的环的入口结点。 思路一： 用map或者set，遍历链...
