给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返回 false
package com.loo;
import java.util.Set; import java.util.LinkedHashSet;
public class LoopPointer { public static void main(String[] args) { ListNode head = new ListNode(0); ListNode l1 = new ListNode(1); ListNode l2 = new ListNode(2); ListNode l3 = new ListNode(3); ListNode l4 = new ListNode(4); ListNode l5 = new ListNode(5); ListNode l6 = new ListNode(6); head.next = l1; l1.next = l2; l2.next = l3; l3.next = l4; l4.next = l5; l5.next = l6; l6.next = l2; System.out.println(hasLoopPointer(head)); // hash表 System.out.println(slowAndFastLoopPointer(head)); // 快慢指针 }
static class ListNode { int value; ListNode next; public ListNode(int v) { value = v; } }
public static boolean hasLoopPointer(ListNode node) { Set<ListNode> set = new LinkedHashSet<ListNode>(); while (node!=null) { if (set.contains(node)) { return true; } set.add(node); node = node.next; } return false; }
public static boolean slowAndFastLoopPointer(ListNode node) { if (node==null) { return false; } ListNode s = node; ListNode f = node.next; while (f!=null && f.next!=null) { if (s.equals(f)) { return true; } s = s.next; f = f.next.next; } return false; } }
