Interview Basics: Reverse a Linked List

Interview Basics: Reverse a Linked List

Reversing a linked list is a very common task in technical interviews. That’s why we devote a whole section of Interview Practice to them! Being able to solve this question easily is a great way to demonstrate to an interviewer that you’re a capable, competent programmer. Let’s discuss two different ways of reversing the direction of a linked list: recursively and iteratively.Linked list refresher

A linked list can be modeled by Node objects, where each node stores a value and a next pointer to the next node in the list. The last node in the list points to NULL, to indicate that you’ve reached the end of the list. You access the linked list by having access to a head pointer at the beginning of the list.

Basic Linked List
A basic linked list

You need to apply a function reverse(head) that does two things:

  1. Reverses the direction of the arrows, changing the structure of the linked list, and
  2. Returns a pointer to the new beginning of the list.

So all the nodes will stay in place in memory, and only the direction of the pointers will change.

Linked List Reversed
What we want to get

You probably wouldn’t implement a linked list this way in an actual program. There might be a lot of different references to the linked list before you reverse it.

Linked List Multiple References
A linked list with multiple references

If you call reverse(head1), you would update head1. But all the other pointers would then be stuck at the end of the linked list, and only head1 would be a good head pointer.

Linked List Reversing With Multiple References
Only head1 was reversed

To get around this, you could make a LinkedList class, or a sentinel head that external references could point to that contains the pointer to the beginning of the linked list. Then you could safely update this reference without breaking any external references.

Linked List with Sentinel Head
A linked list with a sentinel head

But so that we can focus on just the core algorithm, the solutions in this video use a simple version of the linked list.

Why is reversing a linked list tricky?

Linked lists are designed to be easy to traverse in the forward direction, and once a node passes a particular point there is no way of going back to it. If you were in a position where reversing order was something you needed to do often, then a linked list would be a poor choice of data structure and you’d be better off choosing something else.

So this isn’t a problem that you’d really ever encounter on the job. In technical interviews, though, this kind of question is asked as a way of assessing how well you can perform tricky manipulations. That’s why sometimes the problems that interviewers ask can feel kind of artificial.

In this video, I demonstrate two different approaches to reversing a linked list: a recursive one, and an iterative one.

The code

Comments are closed.