141. Linked List Cycle

LeetCode easy оригинал: C# #csharp #easy #hash-table #leetcode #linked-list #queue

LeetCode Static

Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.

Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.

Верните true, если в связном списке есть цикл. В противном случае верните false.

Пример:

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

C# решение

сопоставлено/оригинал

public class Solution {
    public bool HasCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
        ListNode current = head;
        while (current != null) {
            if (nodesSeen.Contains(current)) {
                return true;
            }
            nodesSeen.Add(current);
            current = current.next;
        }
        return false;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool HasCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
        ListNode current = head;
        while (current != null) {
            if (nodesSeen.Contains(current)) {
                return true;
            }
            nodesSeen.push_back(current);
            current = current.next;
        }
        return false;
    }
}

Java решение

сопоставлено/оригинал

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodesSeen = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (nodesSeen.contains(current)) {
                return true;
            }
            nodesSeen.add(current);
            current = current.next;
        }
        return false;
    }
}

JavaScript решение

сопоставлено/оригинал

var hasCycle = function (head) {
    let nodesSeen = new Set();
    let current = head;
    while (current != null) {
        if (nodesSeen.has(current)) {
            return true;
        }
        nodesSeen.add(current);
        current = current.next;
    }
    return false;
};

Python решение

сопоставлено/оригинал

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

Go решение

сопоставлено/оригинал

func hasCycle(head *ListNode) bool {
    nodesSeen := make(map[*ListNode]bool)
    current := head
    for current != nil {
        if nodesSeen[current] {
            return true
        }
        nodesSeen[current] = true
        current = current.Next
    }
    return false
}

Algorithm

1️⃣

Инициализация структуры данных:

Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы.

2️⃣

Обход списка:

Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди.

3️⃣

Проверка на цикл:

Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false.

Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true.

Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.