An intern approached me for help in one of their past exam questions. They said they had already turned in the exam but just wanted to know the answer. The question was not that hard and I had a bit of time to kill so I helped them.

Me: So, to make it O(n), you have to make it a double linked list, and keep a tail.

Them: But the problem requires us to solve it with a single liked list.

Me: You can just iterate it at the end to make it single-linked again. That costs O(n), so the solution is still O(n).

Them: Oh yeah right. I don't think we even need a tail though, we could just have a variable pointing to the last link.

Me: ...which is called a tail.

  • 2
    Ah, those times when you know a term but not what it means.

    The funny feeling of trying to excuse to yourself why you thought it meant something else...
  • 0
    Are they asking if they can use nullptr instead of an object for the tail?
Add Comment