Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer poswhich represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
解法一：哈希表
时间 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 boolean hasCycle(ListNode head) { Map<ListNode,Integer> map = new HashMap<>(); int i=0; while(head != null){ if(map.containsKey(head)) return true; map.put(head,i); head = head.next; i++; } return false; } }
解法二：很巧妙的用两个指针，一快一慢。
runner每次跨两步，walker每次跨一步。如果有circle的话一定会有一天runner追上walker
时间 O（n） 空间 O（1）
public class Solution { public boolean hasCycle(ListNode head) { if(head == null) return false; ListNode walker = head; ListNode runner = head.next; while(walker != runner) { if(runner ==null || runner.next == null){ return false; } walker = walker.next; runner = runner.next.next; } return true; } }
leetcode 141. Linked List Cycle
原文：https://www.cnblogs.com/jamieliu/p/10351186.html