Exploration of a really simple linked list and how to find cycles in it.

cycles.swift

//: Playground - noun: a place where people can play

import UIKit

class Node<T: Equatable> {
    typealias NodeType = Node<T>

    let value: T
    var next: NodeType? = nil

    public init(value: T) {
        self.value = value
    }
}

extension Node: Equatable {
    static func ==(lhs: Node, rhs: Node) -> Bool {
        return lhs.value == rhs.value
    }
}

extension Node: CustomStringConvertible {
    var description: String {
        return "Node(\(self.value))"
    }
}

/**
 This is a preposterous simple linked list implentation.
 The only intention of it is to illstrate how to find loops
 */
class LinkedList<T: Equatable> {
    typealias NodeType = Node<T>

    // TODO: We should add ivars for head, tail and even count
    var head: NodeType?

    init<S: Sequence>(_ elements: S) where S.Iterator.Element == T {
        for element in elements {
            self.preppend(value: element)
        }
    }
}

extension LinkedList {
    func preppend(value: T) {
        let node = NodeType(value: value)
        if let head = self.head {
            node.next = head
        }
        self.head = node
    }
}

extension LinkedList {
    func detectCycle() -> Bool {
        var slow:NodeType? = self.head
        var fast:NodeType? = self.head
        var found = false
        while slow != nil && fast != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if let s = slow, let f = fast {
                // We are assuming that the list contains nodes with unique values.
                // If the assumption doesn't hold, we would need to modify
                // the Equatable implementation Node to use something besides the IDs.
                if s == f {
                    found = true
                    break
                }
            }
        }
        return found
    }
}

// Let's produce a list
let l:[Int] = Array(1...10)

// And with it, creates to Linked list
let cyclicLinkedList = LinkedList(l)
let acyclicLinkedList = LinkedList(l)

// … and then, convert cyclicLinkedList to contains a loop.
var node:Node<Int>? = cyclicLinkedList.head
while true {
    if let next = node?.next {
        node = next
    } else {
        break
    }
}

if let node = node {
    node.next = cyclicLinkedList.head
}

if cyclicLinkedList.detectCycle() {
    print("We found a cycle")
}
if !acyclicLinkedList.detectCycle() {
    print("There is no cycle here")
}