【原】刻意练习：LeetCode实战 -- Task09. 环形链表

背景

本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了 三个简单、两个中等、一个困难 等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：链表

链表（Linked List） 是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里除了存放本身数据（data fields）之外还存放其后继节点的指针（Pointer）。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

---

题目

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

---

实现

第一种：利用Hash的方式

通过检查一个结点此前是否被访问过来判断链表是否为环形链表。

• 状态：通过

• 执行用时：172 ms, 在所有 C# 提交中击败了 8.84% 的用户

• 内存消耗：26.9 MB, 在所有 C# 提交中击败了 5.17% 的用户

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution 
{
    public bool HasCycle(ListNode head) 
    {
        HashSet<ListNode> hashSet = new HashSet<ListNode>();
        hashSet.Add(head);

        while (head != null)
        {
            head = head.next;
            if (head == null)
                return false;
            if (hashSet.Contains(head))
                return true;
            hashSet.Add(head);
        }
        return false;        
    }
}


Python 语言

• 执行结果：通过

• 执行用时：88 ms, 在所有 Python3 提交中击败了 16.80% 的用户

• 内存消耗：16.9 MB, 在所有 Python3 提交中击败了 7.04% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        hashset = set()
        hashset.add(head)
        while head is not None:
            head = head.next
            if head is None:
                return False
            if head in hashset:
                return True
            hashset.add(head)
        return False


第二种：利用双指针的方式

• 状态：通过

• 执行用时: 112 ms, 在所有 C# 提交中击败了 98.43% 的用户

• 内存消耗: 24.9 MB, 在所有 C# 提交中击败了 5.13% 的用户

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null)
        {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                return true;
        }
        return false;
    }
}


Python 语言

• 执行结果：通过

• 执行用时：56 ms, 在所有 Python3 提交中击败了 60.97% 的用户

• 内存消耗：16.6 MB, 在所有 Python3 提交中击败了 11.81% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast = head
        slow = head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False


---

来源

• https:///problems/linked-list-cycle/submissions/

---