Interview question that became a meme

How to reverse a linked list?

Yep! This headline says it all. For some reason, for quite a while, this was (hopefully it’s no longer) a very popular problem given during technical interviews. Why that might be? Probably because it’s a simple problem to solve, interviewers don’t have to prepare themselves to use it and it has a couple of solutions so, it’s a good conversation starter about algorithms and performance in regards to time & space complexity. On top of that there’s possibility to follow up on the question, ask about detecting cycles in the list, cache friendliness, so on and so forth. But obviously, prior to solving the problem itself, the candidate has to come up with the implementation of the linked list.

How would you implement a linked list in C++?

You shouldn’t! End of story. In the interview environment of course, you need some context and that’s probably the reason why linked list implementation has become a subtask of the actual list reversal test task. In modern C++, well not even modern, since std::list implementation is part of STL since the very beginnings of the language, you should ALWAYS rely on STL provided containers. People a lot smarter than you and me, already solved the problem you’re trying to solve yourself in the most efficient way possible. There’s no need to reinvent the wheel. But what if you’re starting with a blank canvas and have to continue with this exercise anyway? Well, in such case, there’s little choice but it doesn’t mean you can’t have some fun with it! Let’s have a quick walk-through.

The list itself

In most leetcode problems, you’re given a declaration of the node, somewhat similar to the following one:

1
2
3
4

struct Node {
    int value;
    Node* next;
};

There’s obviously a lot to improve on that (and potentially ran out of time during the interview :)). Let’s incorporate three changes that will instantly make it a more reliable implementation:

• generalisation (through templates),
• memory management,
• encapsulation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

template <typename ValueT>
class Node {
public:
    explicit Node(ValueT value, std::unique_ptr<Node<ValueT>> next) :
        value{std::move(value)},
        next{std::move(next)}
    {
    }

    const ValueT& get() const noexcept {
        return value;
    }

    std::unique_ptr<Node<ValueT>> resetNext() {
        return std::move(next);
    }

    void setNext(std::unique_ptr<Node<ValueT>> node) {
        next = std::move(node);
    }

private:
    const ValueT value;
    std::unique_ptr<Node<ValueT>> next;
};

Looks a bit better doesn’t it? Well, the mentioned problems have been solved but this implementation still isn’t perfect.

Death by recursion

It may not be apparent on first glance but this implementation of Node has a size limit, defined by stack depth. Imagine what’s gonna happen on destruction? During destruction, next variable’s destruction will be performed, after that next->next variable destruction will be performed so on and so forth until we reach the very last node in the list. Since the destruction is a recursive operation, if the list is longer than the stack can accommodate, it’ll end up with a crash (although it’s very likely that modern compilers will understand what’s happening here and will optimise the recursive destruction away automatically).

Memory management problem: iterative destruction

The following destructor will perform an iterative destruction:

1
2
3
4
5

~Node() {
    for (auto c = std::move(next); c; c = std::move(c->next))
    {
    }
}

This line of code is a bit cryptic but in essence it’s very simple. Current node’s next can’t be destroyed as it would trigger the recursive avalanche. Instead, c is replaced with it’s next pointer - the result is that c->next becomes nullptr (due to move operation; thus breaking the recursive destruction) and at the same time, since c has been overwritten, it’s gonna be destroyed.

Let’s add one more function to the Node:

1
2
3
4
5

void visitAll(std::function<void(const ValueT&)> callback) {
    for (auto n = this; n != nullptr; n = n->next.get()) {
        callback(n->value);
    }
}

visitAll will allow for seamless list traversal, it accepts a callback that will be executed on every Node onwards.

The list itself

Bare Node is not something convenient to work with. Let’s wrap it up with a container type:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

template <typename ValueT>
class List {
public:
    void emplace_back(ValueT v) {
        append(std::make_unique<Node<ValueT>>(v, nullptr));
    }

    void append(std::unique_ptr<Node<ValueT>> node) {
        if (!head || !tail) {
            head = std::move(node);
            tail = head.get();
            len = 0;
        } else {
            const auto newTail = node.get();
            tail->setNext(std::move(node));
            tail = newTail;
        }

        len++;
    }

    void prepend(std::unique_ptr<Node<ValueT>> node) {
        node->setNext(std::move(head));
        head = std::move(node);
        len++;
    }

    void traverse(std::function<void(const ValueT&)> callback) {
        if (head) {
            head.visitAll(callback);
        }
    }

private:
    std::unique_ptr<Node<ValueT>> head;
    Node<ValueT>* tail{nullptr};
    std::size_t len{0};
};

The reversal

Now, it should be well out of allotted interview time, but since I’ve implemented this beautiful container, now is a good moment to actually perform some operations on it. I’ll add the reverse operation on the list:

1
2
3
4

void reverse() {
    tail = head.get();
    head = reverse(std::move(head));
}

After reversal, the current head will become list’s tail so prior to the reversal the pointer is being updated. The reversal operation is delegated to reverse overload accepting unique pointer as a sole argument.

Recursively

All recursive problems have to be reduced to a base case first. The base case here is incredibly simple. A reversed list containing a single node is the same as the original list itself:

1
2
3
4

auto next = n->resetNext();
if (!next) {
    return n;
}

Now, the recursion. The list has to be divided into two parts head - the first node, and the rest of the list. The reversal happens by appending current head to reversed remainder of the list. The full implementation looks as so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

std::unique_ptr<Node<ValueT>> reverse(std::unique_ptr<Node<ValueT>> n) {
    auto next = n->resetNext();
    if (!next) {
        return n;
    }

    auto nextBare = next.get();
    auto reversed = reverse(std::move(next));
    nextBare->setNext(std::move(n));
    return reversed;
}

Since we’re dealing with recursion, this implementation suffers from the same inherent problem as with recursive destruction, the space complexity is linear and if list is too long, the reverse operation will cause stack depletion.

Iteratively

1
2
3
4
5
6
7
8
9

std::unique_ptr<Node<ValueT>> reverse(std::unique_ptr<Node<ValueT>> n) {
    List<ValueT> newList;
    while (n) {
        auto next = n->resetNext();
        newList.prepend(std::move(n));
        n = std::move(next);
    }
    return std::move(newList.head);
}

This implementation is superior in terms of space complexity. On first glance, it looks like there are two lists but in fact it’s just rearranging nodes. The original list gets shorter, the temporary list gets longer. In a sense the newList is acting as a stack with a handle to its very bottom.

Full list implementation looks like so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

template <typename ValueT>
class List {
public:
    void emplace_back(ValueT v) {
        append(std::make_unique<Node<ValueT>>(v, nullptr));
    }

    void append(std::unique_ptr<Node<ValueT>> node) {
        if (!head || !tail) {
            head = std::move(node);
            tail = head.get();
            len = 0;
        } else {
            const auto newTail = node.get();
            tail->setNext(std::move(node));
            tail = newTail;
        }

        len++;
    }

    void prepend(std::unique_ptr<Node<ValueT>> node) {
        node->setNext(std::move(head));
        head = std::move(node);
        len++;
    }

    void traverse(std::function<void(const ValueT&)> callback) {
        if (head) {
            head.visitAll(callback);
        }
    }

    void reverse() {
        tail = head.get();
        head = reverse(std::move(head));
    }

private:
    std::unique_ptr<Node<ValueT>> head;
    Node<ValueT>* tail{nullptr};
    std::size_t len{0};

    std::unique_ptr<Node<ValueT>> reverse(std::unique_ptr<Node<ValueT>> n) {
        auto next = n->resetNext();
        auto nextBare = next.get();
        if (!next) {
            return n;
        }

        auto reversed = reverse(std::move(next));
        nextBare->setNext(std::move(n));
        return reversed;
    }

    std::unique_ptr<Node<ValueT>> reverseIterative(std::unique_ptr<Node<ValueT>> n) {
        List<ValueT> newList;
        while (n) {
            auto next = n->resetNext();
            newList.prepend(std::move(n));
            n = std::move(next);
        }

        return std::move(newList.head);
    }
};