1

I'm trying function that detects a loop/cycle in a linked list using Swift. Can somebody show me code how to do that? The only answers I did find where in some other programming languages that I'm not really familiar

This is the code I was working on so far.

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)
    }
}
Ilija
  • 55
  • 11
  • 1
    Take a look at [this](https://stackoverflow.com/questions/2663115/how-to-detect-a-loop-in-a-linked-list?rq=1) implementation of Floyd's algorihtm (what Scott Hunter refers to below). It's not swift, but you should be able to port it easily. – 500 - Internal Server Error Sep 03 '19 at 13:25
  • There is no reason to mark this question as duplicate as its clearly not! As I said the answers in other programming languages but I'm not familiar with them. So can somebody help me out how to do it in Swift? – Ilija Sep 03 '19 at 13:36
  • What part(s) of Floyd's algorithm do you need help with? What have you tried? – Scott Hunter Sep 03 '19 at 13:38
  • The linked-to question is language agnostic, and the answers explain the algorithm (with links to further documentation). The examples are in Java etc, but once you to understand the *idea* it should be easy to implement in Swift. – Martin R Sep 03 '19 at 13:40

1 Answers1

3

One way is to traverse the list, somehow keeping track of the nodes previously visited; eventually, you will either visit a previously-visited node (and thus know there is a loop) or hit the end (and know there is not).

A more clever approach is to traverse the list with 2 pointers, but have one travel twice as fast as the other. If there is a loop, at some point the faster pointer will catch up to the slower one within the loop, so there is no explicit need to keep track of previously visited nodes.

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • If I am right, for cycles of odd length (or is it even ?) the pointers could miss each other. So it might be necessary to compare to the current and next pointers. –  Sep 03 '19 at 13:43
  • Thanks, Scott you helped me a lot – Ilija Sep 03 '19 at 13:57
  • Basically, this was the answer: public mutating func containsCycle(firstNode: Node) -> Bool { var slowRunner = firstNode var fastRunner = firstNode while let nextSlowRunner = slowRunner.next, let nextFastRunner = fastRunner.next?.next { slowRunner = nextSlowRunner fastRunner = nextFastRunner if fastRunner === slowRunner { return true } } return false } } – Ilija Sep 03 '19 at 13:59
  • Or, in English: don't think of the *fast* pointer as *skipping* a node, but traversing (and *checking*) 2 nodes for each 1 the *slow* pointer does. – Scott Hunter Sep 03 '19 at 14:09
  • @yves: No. You move slow first. The only way fast could skip over slow is if it were exactly one behind slow before it was double-incremented. But since slow is moved first, that would mean fast and slow were at the same point before slow was incremented, and that would already have been detected. – rici Sep 03 '19 at 14:57