环形链表
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。否则,返回 false 。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
解法一:哈希表
Set<ListNode> seen = new HashSet<>();
boolean add = seen.add(head);
seen.add(head)方法返回一个布尔值,如果Set中已存在元素,则再次添加会返回false
1、定义一个Set集合
2、遍历节点,若节点能添加到Set集合中,head指向下一个节点,若不能添加到Set集合中(说明集合中已经有该节点了),return true
解法二:双指针
链表的基础问题,链表的特点是每个节点只知道下一个节点,所以一个指针是无法判断链表中是否含有环。如果链表不含环,那么这个指针最终会遇到空指针null,表示链表到头了。判断单链表是否含环,经典解法就是双指针,一个跑得快,一个跑得慢。如果含有环,快指针最终会超慢指针一圈,和慢指针相遇,说明链表含有环。(快指针步长为2,慢指针步长为1)
1、定义两个指针,快指针fast,慢指针slow
2、遍历节点,让快节点每次前进两步,慢指针每次前进一步
3、如果含有环,快指针最终会超慢指针一圈,和慢指针相遇
package od; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; /** * 环形链表(2种解法) * 给你一个链表的头节点head, 判断链表中是否有环。 * 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 * 注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 * 如果链表中存在环 ,则返回 true 。否则,返回 false * 原文地址:https://www.codernav.com/2834.html * 更多算法详解:https://www.codernav.com */ public class OdTest28 { public static void main(String[] args) { // 定义链表 ListNode node5 = new ListNode(5, null); ListNode node4 = new ListNode(4, node5); ListNode node3 = new ListNode(3, node4); ListNode node2 = new ListNode(2, node3); ListNode node1 = new ListNode(1, node2); // 定义环形链表,将node5指向node3 node5.next = node3; // 哈希表 boolean exist1 = f1(node1); System.out.println(exist1); // 双指针 boolean exist2 = f2(node1); System.out.println(exist2); // ArrayList boolean exist = f(node1); System.out.println(exist); } public static boolean f(ListNode head) { List<ListNode> list = new ArrayList<>(); while (head != null) { // 集合中已经存在node了,说明之前已经出现过了,该节点被指向两次 if (list.contains(head)) { return true; } // 如果集合中没有,将当前节点存入集合 list.add(head); // 当前节点指向下一个节点继续遍历 head = head.next; } return false; } public static boolean f1(ListNode head) { Set<ListNode> seen = new HashSet<>(); while (head != null) { // boolean add = seen.add(head);该方法返回一个布尔值,如果Set中已存在元素,则再次添加会返回false if (!seen.add(head)) { return true; } // 当前节点指向下一个节点继续遍历 head = head.next; } return false; } public static boolean f2(ListNode head) { //初始化快慢指针指向头节点 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { //快指针每次前进两步 fast = fast.next.next; //慢指针每次前进一步 slow = slow.next; // 如果含有环,快指针最终会超慢指针一圈,和慢指针相遇 if (fast == slow) { return true; } } return false; } } class ListNode { int val; ListNode next; ListNode(int val, ListNode next) { this.val = val; this.next = next; } }