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:
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:
null at the beginning isn't the head. I've put it there to make the diagram more understandable.
- We set the
currentpointer to the
null(depending on your programming language).
- We set the
current.next. Think about what happens if we don't do this step.
- We set the
previous; essentially turning the link from → to ←.
- We move the
currentand then we move the
currentpointer up one element.
current = current.next. If we move the
currentelement first, we will lose our reference to that node!
class LinkedListNode: def __init__(self, value, next_node): self.value = value self.next_node = next_node def reverse_linked_list(head: LinkedListNode): 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 current = self.head # initialize temporary = None previous = None # walk through the linked list while (current != None): # don't let go of your chain! temporary = current.next # swap the link direction 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 self.head = previous
Ah, this makes more sense in that context; thanks for the clarification! Yes, for me I was specifically practicing building a linked list stack from scratch and wanted to implement a reverse method.
Also, I'm pretty new with Python so I'm not sure what is going on with the argument in this line:
Is that setting a default argument if no parameters were called?