本篇图文是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% 的用户
/**
* 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% 的用户
# 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% 的用户
/**
* 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% 的用户
# 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://leetcode-cn.com/problems/linked-list-cycle/submissions/
联系客服