Discussion on "Crushing Tech Interviews with the Linked List Reversal Pattern"

Sloth · 2021-04-13T15:56:53.169Z

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...

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, I assume that what you're showing me is the reverse method within a LinkedList class.

Like you've already mentioned, my solution will just return the new head; I'm not adding a method to a linked list class.

Both solutions are correct and to be fair if this was the real world, the reverse method on the linked list class would definitely be the way to go.

However, if the question they're asking is:

Given a head node of a linked list, reverse the linked list

You would most likely be better off writing a function that has the following signature:

reverse_linked_list(head: LinkedListNode) -> LinkedListNode:

However, if the question is:

Create a LinkedList class with a reverse() method which will reverse the pointers of all the nodes in the list

then you definitely go for your approach.

Thanks for reading!

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

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

Search Hashnode

Crushing Tech Interviews with the Linked List Reversal Pattern

Responses1