8
\$\begingroup\$

I am writing a piece of code for some students and I came up with the following implementation of Floyd's algorithm for finding cycles in linked lists.

I was wondering if there are ways I can improve what I have so far such that the result is

  • more C++ idiomatic
  • does not contain dumb mistakes associated with the generic code
template <typename T>
struct Node {
    T val;
    Node* next;
    Node() = default;
    Node(T x)
        : val(x)
        , next(nullptr)
    {
    }
};

template <typename T>
Node<T>* detect_cycle_constant_time(Node<T>* head)
{
    Node<T> *n1, *n2;
    n1 = n2 = head;

    while (n1 && n2) {
        n1 = n1->next;
        n2 = n2->next;
        if (n2)
            n2 = n2->next;
        else
            break;

        if (n1 == n2)
            break;
    }

    // second phase of Floyds's algorithm
    if (n1 == n2) {
        n2 = head;
        while (n1 != n2) {
            n1 = n1->next;
            n2 = n2->next;
        }
        return n1;
    }
    return nullptr;
}
\$\endgroup\$

2 Answers 2

Reset to default
7
\$\begingroup\$

General

I found no "dumb mistakes associated with generic code". Good job.

Still, there are some points which can be improved.
(Aren't there always?)

The first point is encapsulation.

Letting nodes float around free, instead of keeping them in their dedicated container, or (rarely) evacuating them to a handle for re-insertion, is not recommended.

Admittedly, a properly written container won't suddenly sprout a cycle, so there you are.

Also, it would detract from the point of your code, so let's leave it alone this time.

Node

Node's default ctor won't initialize its members. The fix is easy:
Just add in-class initializers.

Doing so even allows you to simplify your second constructor, removing the second mem-initializer.

That is, if Node should even have anything but its data members. I personally prefer to have my Node's not getting in the way when implementing my containers.

Floyd's algorithm

The name detect_cycle_constant_time() is a bald-faced lie. The algorithm needs linear time in the number of nodes.

Doing an early return would simplify your code. As you don't allocate any resources, there goes the only argument against. Doing data-flow analysis is much more involved.

There are more loops than the humble while-loop. Sometimes, they are even useful.

Using auto would slightly simplify your local variable definitions.

Whether to use class or typename for template arguments is a matter of taste. All else being equal, I prefer brevity.

Modified Code

template <class T>
struct Node {
    T val = T();
    Node* next = nullptr;
    Node() = default;
    Node(T x) : val(x) {}
};

template <class T>
Node<T>* detect_cycle_floyd(Node<T>* head)
{
    auto n1 = n2 = head;

    do {
        if (!n2)
            return n2;
        n1 = n1->next;
        n2 = n2->next;
        if (!n2)
            return n2;
        n2 = n2->next;
    } while (n1 != n2);

    // second phase of Floyds's algorithm
    for (n2 = head; n1 != n2; n2 = n2->next)
        n1 = n1->next;
    return n1;
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Still, there are some points which can be improved -> Aren't there always? Love it \$\endgroup\$ Commented Nov 17, 2020 at 13:14
  • \$\begingroup\$ The name is pure (copy and paste like mistake) dumbness. \$\endgroup\$ Commented Nov 17, 2020 at 14:24
  • \$\begingroup\$ Would it be good to also add support for non copy able and/or non default constructable types? For instance unique_ptr? \$\endgroup\$ Commented Nov 17, 2020 at 14:27
  • \$\begingroup\$ @DavideSpataro C&P gets to the best of us. As well as half-assed hasty and half-asleep rewrites. To support non-copyable, non default-constructible, expensive and other interesting types, my node-class is pretty much always a completely dumb sack of data. For various reasons, it is always composed of a links-struct (or single pointer) as the first member, and the payload as the second. \$\endgroup\$ Commented Nov 17, 2020 at 14:39
4
\$\begingroup\$

In addition to everything mentioned in Deduplicator's answer: there's no good reason to force the caller to pass a pointer to a modifiable node, as we should only be reading. I'd expect a signature more like

template <typename T>
Node<T> const* detect_cycle(Node<T> const* head);

I would have liked to have seen some unit tests for this code, to prove that the behaviour is as advertised!

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.