如何使用 Swift 检测链表中的循环/循环

Question

我正在尝试使用 Swift 检测链表中的循环/循环的函数。 有人可以告诉我代码如何做到这一点吗？ 我确实在其他一些我不太熟悉的编程语言中找到的唯一答案

这是我到目前为止正在处理的代码。

public class Node<Value> {
public var value: Value
public var next: Node?
public init(value: Value, next: Node? = nil) {
self.value = value
self.next = next
}
}
public struct LinkedList<Value> {
public var head: Node<Value>?
public var tail: Node<Value>?
public init() {}
public var isEmpty: Bool {
return head == nil
}
public mutating func push(_ value: Value) {
head = Node(value: value, next: head)
if tail == nil {
tail = head
}
}
public mutating func apped(_ value: Value) {
guard !isEmpty else {
push(value)
return
}
tail!.next = Node(value: value)
tail = tail!.next
}
}
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "(value)"
}
return "(value) -> "  + String(describing: next) + " "
}
}
extension LinkedList: CustomStringConvertible {
public var description: String {
guard let head = head else {
return "Empty List"
}
return String(describing: head)
}
}

Answer 1

一种方法是遍历列表，以某种方式跟踪以前访问过的节点;最终，您将访问以前访问过的节点(因此知道存在循环(或点击末尾(并且知道没有(。

更聪明的方法是使用 2 个指针遍历列表，但让一个指针的行进速度是另一个指针的两倍。 如果存在循环，则在某个时候，较快的指针将赶上循环中较慢的指针，因此无需明确跟踪以前访问过的节点。