<commit_before>---
layout: post
title: LeetCode 141
category: 技术
tags: LeetCode Easy
keywords: LeetCode
description: 2019 每天一道题 #141
---

#### [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
---
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 `pos` which 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.
```
![e1](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)

**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.
```
![e2](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)

**Example 3:**
```
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
```
![e3](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)
 

**Follow up:** Can you solve it using `O(1)` (i.e. constant) memory?

---
#### Thoughts
---
Though this is so call an 'easy' question, I still spend more than one hour to do this.   
My first thought was using two pointer, one start from the head, another start from head.next, do `sec = sec.next` while `sec.next != first`, however I couldn't find the timing for `first = first.next`, this results in Runtime error.  
At the end, someone reminded me that I can reuse the solution of [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/), that's how I got this done.

**First try:**
```Java
public class Solution {
    public boolean hasCycle(ListNode h) {
        if(h == null || h.next == null)
            return false;
        ListNode fi = h;
        ListNode sec = fi;
        while (sec != null) {
            fi = fi.next;
            sec = sec.next == null ? null : sec.next.next;
            if(sec != null && sec.next == fi)
                return true;
        }
        return false;
    }
}
```

**Result 1:**
> Runtime: **1 ms**, faster than **32.43%** of Java online submissions for Linked List Cycle.  
> Memory Usage: **38.4 MB**, less than **100.00%** of Java online submissions for Linked List Cycle.

The time complexity is quite confusing when there's a loop, the calculation can be see [here](https://leetcode.com/problems/linked-list-cycle/solution/).

**Second try:**

**Result 2:**

<commit_msg>Update 2019-02-20-LeetCode-141.md<commit_after>---
layout: post
title: LeetCode 141
category: 技术
tags: LeetCode Easy
keywords: LeetCode
description: 2019 每天一道题 #141
---

#### [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
---
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 `pos` which 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.
```
![e1](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)

**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.
```
![e2](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)

**Example 3:**
```
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
```
![e3](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)
 

**Follow up:** Can you solve it using `O(1)` (i.e. constant) memory?

---
#### Thoughts
---
Though this is so call an 'easy' question, I still spend more than one hour to do this.   
My first thought was using two pointer, one start from the head, another start from head.next, do `sec = sec.next` while `sec.next != first`, however I couldn't find the timing for `first = first.next`, this results in Runtime error.  
At the end, someone reminded me that I can reuse the solution of [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/), that's how I got this done.

**First try:**
```Java
public class Solution {
    public boolean hasCycle(ListNode h) {
        if(h == null || h.next == null)
            return false;
        ListNode fi = h;
        ListNode sec = fi;
        while (sec != null) {
            fi = fi.next;
            sec = sec.next == null ? null : sec.next.next;
            if(sec != null && sec.next == fi)
                return true;
        }
        return false;
    }
}
```

**Result 1:**
> Runtime: **1 ms**, faster than **32.43%** of Java online submissions for Linked List Cycle.  
> Memory Usage: **38.4 MB**, less than **100.00%** of Java online submissions for Linked List Cycle.

The time complexity is quite confusing when there's a loop, the calculation can be see [here](https://leetcode.com/problems/linked-list-cycle/solution/).

**Second try:**

Review on 2019-03-16, same idea with the first one.
```Java
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast != null && fast.next != null && fast.next == slow)
                return true;
        }
        return false;
    }
}
```
**Result 2:**
> Runtime: **0 ms**, faster than **100.00%** of Java online submissions for Linked List Cycle.  

{'fraction_non_alphanumeric': 0.13735602544266803, 'fraction_numerical': 0.030428055698813822, 'mean_word_length': 3.1145685997171144, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 8, 'https://': 12, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5886889', 'n_tokens_mistral': 1958, 'n_tokens_neox': 1785, 'n_words': 705}