|
| 1 | +####141. 环形链表 |
| 2 | + |
| 3 | +难度：简单 |
| 4 | + |
| 5 | +--- |
| 6 | + |
| 7 | +给你一个链表的头节点`head` ，判断链表中是否有环。 |
| 8 | + |
| 9 | +如果链表中有某个节点，可以通过连续跟踪`next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数`pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：`pos` 不作为参数进行传递** 。仅仅是为了标识链表的实际情况。 |
| 10 | + |
| 11 | +_如果链表中存在环_ ，则返回`true` 。 否则，返回`false` 。 |
| 12 | + |
| 13 | +**示例 1：** |
| 14 | + |
| 15 | + |
| 16 | + |
| 17 | +``` |
| 18 | +输入：head = [3,2,0,-4], pos = 1 |
| 19 | +输出：true |
| 20 | +解释：链表中有一个环，其尾部连接到第二个节点。 |
| 21 | +``` |
| 22 | + |
| 23 | +**示例 2：** |
| 24 | + |
| 25 | + |
| 26 | + |
| 27 | +``` |
| 28 | +输入：head = [1,2], pos = 0 |
| 29 | +输出：true |
| 30 | +解释：链表中有一个环，其尾部连接到第一个节点。 |
| 31 | +``` |
| 32 | + |
| 33 | +**示例 3：** |
| 34 | + |
| 35 | + |
| 36 | + |
| 37 | +``` |
| 38 | +输入：head = [1], pos = -1 |
| 39 | +输出：false |
| 40 | +解释：链表中没有环。 |
| 41 | +``` |
| 42 | + |
| 43 | +**提示：** |
| 44 | + |
| 45 | +* 链表中节点的数目范围是`[0, 10^4]` |
| 46 | +*`-10^5 <= Node.val <= 10^5` |
| 47 | +*`pos` 为`-1` 或者链表中的一个**有效索引** 。 |
| 48 | + |
| 49 | +**进阶：** 你能用`O(1)`（即，常量）内存解决此问题吗？ |
| 50 | + |
| 51 | +--- |
| 52 | + |
| 53 | +快慢指针： |
| 54 | + |
| 55 | +慢指针每次移动一个节点，快指针每次移动两个节点。 |
| 56 | + |
| 57 | +快指针总是先于慢指针的遍历。因此在循环中只需要判断快指针及其下一节点是否为空即可，否则如果存在环，快指针总会遇到慢指针。 |
| 58 | + |
| 59 | +```Java |
| 60 | +/** |
| 61 | + * Definition for singly-linked list. |
| 62 | + * class ListNode { |
| 63 | + * int val; |
| 64 | + * ListNode next; |
| 65 | + * ListNode(int x) { |
| 66 | + * val = x; |
| 67 | + * next = null; |
| 68 | + * } |
| 69 | + * } |
| 70 | +*/ |
| 71 | +publicclassSolution { |
| 72 | +publicbooleanhasCycle(ListNodehead) { |
| 73 | +if(head==null|| head.next==null)returnfalse; |
| 74 | +ListNode slow= head, fast= head.next; |
| 75 | +while(slow!= fast){ |
| 76 | +if(fast==null|| fast.next==null)returnfalse; |
| 77 | + slow= slow.next; |
| 78 | + fast= fast.next.next; |
| 79 | + } |
| 80 | +returntrue; |
| 81 | + } |
| 82 | +} |
| 83 | +``` |