loop.swift

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

import Cocoa

class Node<T: Comparable> {
    var next: Node<T>?
    let value: T

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

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

class LinkedList<T: Comparable> {
    private var head: Node<T>?
    private var tail: Node<T>?

    var isEmpty: Bool {
        return self.head == nil
    }

    func append(value: T) -> Node<T> {
        let node = Node<T>(value: value)

        if self.head == nil {
            self.head = node
        }

        if let tail = self.tail {
            tail.next = node
        }
        self.tail = node

        return node
    }

    private func walk(start1: Node<T>, start2: Node<T>, walkFaster: Bool = false) -> Node<T>? {
        var n1 = start1.next
        var n2 = walkFaster ? start2.next?.next : start2.next
        while n1 != nil && n2 != nil && n1!.value != n2!.value {
            n1 = n1!.next
            n2 = walkFaster ? n2!.next?.next : n2!.next
        }
        return n2
    }

    func findLoopStart() -> Node<T>? {
        guard self.containsLoop else {
            return nil
        }
        // The two pointers met themselves k nodes from the loop start
        if let lap = self.walk(start1: self.head!, start2: self.head!, walkFaster: true) {
            // We reset one of the pointers to the list head,
            // and make them both walk at the same speed.
            if let start = self.walk(start1: self.head!, start2: lap, walkFaster: false) {
                // They will meet at the loop start.
                return start
            }
        }
        return nil
    }

    var containsLoop: Bool {
        guard let head = self.head else {
            return false
        }
        return self.walk(start1: head, start2: head, walkFaster: true) != nil
    }
}

extension LinkedList: CustomStringConvertible {
    var description: String {
        var description = ""
        var node = self.head
        while node != nil {
            description += "\(node!.value)"
            node = node!.next
        }
        return description
    }
}

let ll = LinkedList<Int>()
ll.append(value: 0)
ll.append(value: 1)
ll.append(value: 2)
let n = ll.append(value: 3)
ll.append(value: 4)
ll.append(value: 5)
ll.append(value: 7)
ll.append(value: 8)
let k = ll.append(value: 9)

k.next = n

assert(ll.containsLoop)

let start = ll.findLoopStart()

assert(start?.value == 3)