首页 > 代码库 > LeetCode 141. Linked List Cycle
LeetCode 141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
1 /** 2 * Definition for singly-linked list. 3 */ 4 class ListNode { 5 int val; 6 ListNode next; 7 8 ListNode(int x) { 9 val = x;10 next = null;11 }12 }
思路1：
- 遍历链表把所有的节点放入set中
- 若set中包含当前节点，则含有环
- 若set中没有，则把节点放入set
- 取下一个节点
- 若节点为null，则遍历结束，肯定没有环。
代码1：
1 public boolean hasCycleBySet(ListNode head) { 2 Set<ListNode> set = new HashSet<>(); 3 while(head != null){ 4 if(set.contains(head)) 5 return true; 6 else 7 set.add(head); 8 head = head.next; 9 }10 return false;11 }
思路2：
- 遍历链表，一次快（每次获取后面第二个），一次慢（每次获取后面第一个）
- 若快的节点为null或下一个为null，则不包含环
- 在若干次之后，若快的节点与慢的节点相同则包含环。（此时快的遍历比慢的遍历领先了一个链表的长度）
代码2：
1 public boolean hasCycle(ListNode head) { 2 if (head == null || head.next == null) { 3 return false; 4 } 5 ListNode slow = head; 6 ListNode fast = head.next; 7 while (slow != fast) { 8 if (fast == null || fast.next == null) { 9 return false;10 }11 slow = slow.next;12 fast = fast.next.next;13 }14 return true;15 }
扩展：计算环形链表的长度可参考思路二，快慢相差一个链表的长度，相减即可获得长度。
LeetCode 141. Linked List Cycle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。