环形链表 II
题目形容:给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。
为了示意给定链表中的环,咱们应用整数 pos 来示意链表尾连贯到链表中的地位(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。留神,pos 仅仅是用于标识环的状况,并不会作为参数传递到函数中。
阐明:不容许批改给定的链表。
进阶:
你是否能够应用 O(1) 空间解决此题?
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:哈希表
HashSet 判断节点是否反复。
解法二:双指针法
应用快慢节点,如果有环,则这两个节点必回相遇。
import java.util.HashSet;
import java.util.Set;
public class LeetCode_142 {
/**
* 哈希
*
* @param head
* @return
*/
public static ListNode detectCycle(ListNode head) {if (head == null) {return null;}
Set<ListNode> nodes = new HashSet<>();
nodes.add(head);
while (head.next != null) {
// 如果 next 节点在哈希表中呈现过,阐明成环了,而且 next 节点必定是入环点,间接返回
if (nodes.contains(head.next)) {return head.next;}
nodes.add(head.next);
head = head.next;
}
return null;
}
/**
* 双指针法
*
* @param head
* @return
*/
public static ListNode detectCycle2(ListNode head) {if (head == null) {return null;}
ListNode slow = head, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {fast = fast.next.next;} else {return null;}
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
public static void main(String[] args) {ListNode head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = new ListNode(-4);
head.next.next.next.next = head.next;
System.out.println(detectCycle(head) == null ? -1 : detectCycle(head).val);
System.out.println(detectCycle2(head) == null ? -1 : detectCycle2(head).val);
}
}
【每日寄语】 人世间不可意料的事件太多了,然而不管怎样,社会还会照样运行。一个人不论有多大的成就,在世界万物中都是十分渺小的,所以要珍惜每一分每一秒。