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)
    }
}
Improve this question
4
  • 1
    Take a look at this implementation of Floyd's algorihtm (what Scott Hunter refers to below). It's not swift, but you should be able to port it easily. Commented Sep 3, 2019 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? Commented Sep 3, 2019 at 13:36
  • What part(s) of Floyd's algorithm do you need help with? What have you tried? Commented Sep 3, 2019 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. Commented Sep 3, 2019 at 13:40

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

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.
Thanks, Scott you helped me a lot
Basically, this was the answer: public mutating func containsCycle<T>(firstNode: Node<T>) -> 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 } }
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.
@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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.