# Crushing Tech Interviews with the Linked List Reversal Pattern

Ah, a good old linked list problem. Some people love them, some people help them.

Hopefully with this pattern, you'll love questions which ask you to reverse the links between a set of nodes of a linked list. It may sounds like a niche pattern but it's one that comes up time and time again.

So how do we do it?

We reverse a linked list one node at a time. We have three variables: current, previous and temp. Juggling these pointers is what allows you to solve this question.

For each step, we reverse the current node by pointing it's next value to the previous pointer. Simple right? Not so much... we need to be careful when we do this because if we lose a reference to a node, that node is lost! Thats where the temp variable comes into play; to ensure that we're keeping track of everything.

It sounds a bit confusing but let me show you via some diagrams:

Note: the null at the beginning isn't the head. I've put it there to make the diagram more understandable.

1. We set the current pointer to the head value, the temp and previous values to None / null (depending on your programming language).
2. We set the temp value to current.next. Think about what happens if we don't do this step.
3. We set the current.next value to previous; essentially turning the link from → to ←.
4. We move the previous pointer to current and then we move the current pointer up one element. current = current.next. If we move the current element first, we will lose our reference to that node!
def __init__(self, value, next_node):
self.value = value
self.next_node = next_node

previous_node, temp_node, current_node = None, None, head
while current_node is not None:
temp_node = current_node.next_node
current_node.next_node = previous_node
previous_node = current_node
current_node = temp_node
return previous_node

Work through each step one by one and you'll be able to crack it!

Here's some more questions that you can have a crack at:

If you enjoyed this article, please go support the people over at https://www.educative.io/courses/grokking-the-coding-interview I've based this blog post on their content.

Thanks, this was super helpful for me to work through the concept. I couldn't get it working at first, and I realized it was your very last line: return previous_node; I think it might be helpful for you to clarify what you are doing with that line.

What I discovered was that the last item found in the list needs to be explicitly assigned as the list's new head. I guess wherever you are calling reverse_linked_list() in another program you must handle that, which is why you're returning the previous_node. In my implementation, I wanted to handle that new head assignment inside the reverse function, so I ended up with this:

# reverse: reverse the linked list
def reverse(self):

# start at the top of the stack

# initialize
temporary = None
previous = None

# walk through the linked list
while (current != None):

# don't let go of your chain!
temporary = current.next

current.next = previous

# attach current to the next nodes "previous"
previous = current

# step to the "next" node; stored in temp
current = temporary

# once reached the end/bottom of the stack
# it's important to make that bottom item the new head