141. Linked List Cycle

  • 35.6%

https://leetcode.com/problems/linked-list-cycle/description/

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?


方法一:

一个快指针,一个慢指针

My faster and slower runner solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 /**
use faster and lower runner solution. (2 pointers)
the faster one move 2 steps, and slower one move only one step.
if there's a circle, the faster one will finally "catch" the slower one.
(the distance between these 2 pointers will decrease one every time.)

if there's no circle, the faster runner will reach the end of linked list. (NULL)
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
// 除了判断head,还要判断head->next
if(head == NULL || head -> next == NULL)
return false;
// 初始位置都设置为head
ListNode *fast = head;
ListNode *slow = head;
// 要是有环,while循环肯定成立,也肯定会在while里面返回true。
while(fast -> next && fast -> next -> next){
fast = fast -> next -> next;
slow = slow -> next;
if(fast == slow)
return true;
}
// 如果有环,肯定会在上面的while循环里相遇,并返回true的。
return false;
}
};

参考资料:

  1. https://discuss.leetcode.com/topic/4218/my-faster-and-slower-runner-solution

https://discuss.leetcode.com/topic/16098/except-ionally-fast-python

Except-ionally fast Python

Took 88 ms and the “Accepted Solutions Runtime Distribution” doesn’t show any faster Python submissions. The “trick” is to not check all the time whether we have reached the end but to handle it via an exception. “Easier to ask for forgiveness than permission.”

The algorithm is of course Tortoise and hare.

1
2
3
4
5
6
7
8
9
10
def hasCycle(self, head):
try:
slow = head
fast = head.next
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return False

java


https://discuss.leetcode.com/topic/12516/o-1-space-solution

O(1) Space Solution

1
2
3
4
5
6
7
8
9
10
11
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode walker = head;
ListNode runner = head;
while(runner.next!=null && runner.next.next!=null) {
walker = walker.next;
runner = runner.next.next;
if(walker==runner) return true;
}
return false;
}
  1. Use two pointers, walker and runner.
  2. walker moves step by step. runner moves two steps at time.
  3. if the Linked List has a cycle walker and runner will meet at some point.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 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) {
if(head == null) return false;
ListNode slow, fast;
slow = head;
fast = head;
while(fast.next!=null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast)
return true;
}
return false;
}
}
谢谢你,可爱的朋友。