怎么屏蔽ip段访问网站,医院网站建设目的,12306 网站开发,哪里有学电脑培训班问题背景
给定一个链表的头节点 h e a d head head#xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 n u l l null null。 如果链表中有某个节点#xff0c;可以通过连续跟踪 n e x t next next 指针再次到达#xff0c;则链表中存在环。 为了…问题背景
给定一个链表的头节点 h e a d head head返回链表开始入环的第一个节点。 如果链表无环则返回 n u l l null null。 如果链表中有某个节点可以通过连续跟踪 n e x t next next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 p o s pos pos 来表示链表尾连接到链表中的位置索引从 0 0 0 开始。如果 p o s pos pos 是 − 1 -1 −1则在该链表中没有环。注意 p o s pos pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。
数据约束
链表中节点的数目范围在范围 [ 0 , 1 0 4 ] [0, 10 ^ 4] [0,104] 内 − 1 0 5 ≤ N o d e . v a l ≤ 1 0 5 -10 ^ 5 \le Node.val \le 10 ^ 5 −105≤Node.val≤105 p o s pos pos 的值为 − 1 -1 −1 或者链表中的一个有效索引
解题过程
经典找入环节点流程主要分为两个阶段
定义快慢指针用找环的方式让两个指针相遇。复用快指针或者重新定义一个指针从头出发与慢指针同时后移两指针相遇的节点即为入环节点。
不复用快指针的情况下上述流程可以在一个循环里实现时间复杂度是不变的。由于快慢指针相遇时最多完整地遍历一次链表时间复杂度是 O ( N ) O(N) O(N) 量级的需要常数级别的额外空间。
具体实现
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head, fast head, nextTurn head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if(slow fast) {while(slow ! nextTurn) {slow slow.next;nextTurn nextTurn.next;}return slow;}}return null;}
}
