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.

Untitled Notebook-23.jpg

  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!
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:

https://leetcode.com/problems/palindrome-linked-list/ (Easy)

https://leetcode.com/problems/reverse-linked-list-ii/ (Medium)

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.

Comments (4)

Ben Hammond's photo

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
Show +1 replies
Ben Hammond's photo

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: reverse_linked_list(head: LinkedListNode)

Is that setting a default argument if no parameters were called?

Sloth

Sloth's photo

Ben Hammond

Good question!

It's a new feature that was introduced in py 3.5 for type hinting: see here for documentation docs.python.org/3/library/typing.html

Here's a good example of how it works with a type checker called mypy: stackoverflow.com/a/38217786/2311710