142. Linked List Cycle II

leetcode medium

#csharp#hash-table#leetcode#linked-list#medium

Task

Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.

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

Не модифицируйте связный список.

Пример:

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

Output: tail connects to node index 1

Explanation: There is a cycle in the linked list, where tail connects to the second node.

C# solution

matched/original

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
public class Solution {
    public ListNode DetectCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
        ListNode node = head;
        while (node != null) {
            if (nodesSeen.Contains(node)) {
                return node;
            } else {
                nodesSeen.Add(node);
                node = node.next;
            }
        }
        return null;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
public:
    public ListNode DetectCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
        ListNode node = head;
        while (node != null) {
            if (nodesSeen.Contains(node)) {
                return node;
            } else {
                nodesSeen.push_back(node);
                node = node.next;
            }
        }
        return null;
    }
}

Java solution

matched/original

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<>();
        ListNode node = head;
        while (node != null) {
            if (nodesSeen.contains(node)) {
                return node;
            } else {
                nodesSeen.add(node);
                node = node.next;
            }
        }
        return null;
    }
}

JavaScript solution

matched/original

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

var detectCycle = function(head) {
    let nodesSeen = new Set();
    let node = head;
    while (node !== null) {
        if (nodesSeen.has(node)) {
            return node;
        } else {
            nodesSeen.add(node);
            node = node.next;
        }
    }
    return null;
};

Python solution

matched/original

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        nodes_seen = set()
        node = head
        while node is not None:
            if node in nodes_seen:
                return node
            else:
                nodes_seen.add(node)
                node = node.next
        return None

Go solution

matched/original

type ListNode struct {
    Val  int
    Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
    nodesSeen := make(map[*ListNode]bool)
    node := head
    for node != nil {
        if _, ok := nodesSeen[node]; ok {
            return node
        } else {
            nodesSeen[node] = true
            node = node.Next
        }
    }
    return nil
}

Explanation

Algorithm

1️⃣

Инициализация и начало обхода:

Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов.

Начните обход со связного списка, перемещая узел на один шаг за раз.

2️⃣

Проверка на наличие узла в множестве:

Для каждого посещенного узла проверьте, содержится ли он уже в множестве nodes_seen.

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

3️⃣

Добавление узла в множество или завершение обхода:

Если узел не найден в nodes_seen, добавьте его в множество и перейдите к следующему узлу.

Если узел становится равным null (конец списка), верните null. В списке нет цикла, так как в случае наличия цикла вы бы застряли в петле и не достигли бы конца списка.

😎