Miloping

During one interview I was asked to write an algorithm to reverse a singly-linked list. This is a data structure that can only be traversed in one direction, kind of like driving down a one-way street.

It is important to know how a linked list differs from an array. An array can also be used as a list, so when are linked lists more appropriate? I can use an array to store my three favorite numbers: 22, 80, and 3306.

int numbers[3] = {22, 80, 3306};

If tomorrow, I want to add 6881 to my list of favorite numbers then I need to resize the array. Resizing an array means creating a new and bigger array, into which the old array is copied.

So what's different about a linked list? New items can be added to a linked list without it needing to be resized. Everyday I can add a new favorite number until I decide to find a new hobby. Where an array is a single contiguous block of memory, a linked list is a chain of small blocks of memory. Each block in the linked list is called a node.

class Node:
    def __init__(self, value, next = None):
        self.value = value
        self.next = next

Because each node is stored separately, how do we know which ones are part of the same list? Well, each node has a reference to the next node in the list. Like two people holding hands.

boy = Node("Takaki")
girl = Node("Akari")

boy.next = girl

Or maybe not anything like holding hands. Imagine whatever works for you.

It turns out I was so tired from flying in for the interview, got absolutely lost in the pointers and ran out of time. In a follow up email I described an iterative approach.

def iterative_reverse(curr):
    prev = None
    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return curr

Pretty straightforward. Two pointers are used to keep track of the previous node and the next node. I think of the hand-holding picture here. The node lets go of on hand, turns around and holds the hand of another node.

A fellow interviewee had described his approach, a recursive algorithm, he said. I thought, Right right, that's what I should've gone for, would have been so easy. But today, I revisited the problem, and it was so not. It's only been two months and my brain has atrophied.

def recursive_reverse(curr):
    if curr is None:
        return
    next = curr.next
    if next is None:
        return curr
    next = recursive_reverse(next)
    curr.next.next = curr
    curr.next = None
    return next

The first if is a guard clause for a None argument. Each step works on the node in front, and for the current node, we point it to None. Working backwards like this the last node is point to None, which puts it at the end of the list.

>>> first = Node(1, Node(2, Node(3)))
>>> def list(node):
...     while node is not None:
...         yield node
...         node = node.next
>>>
>>> " => ".join([str(n.value) for n in list(first)])
'1 => 2 => 3'
>>> first = iterative_reverse(first)
>>> " => ".join([str(n.value) for n in list(first)])
'3 => 2 => 1'
>>> first = recursive_reverse(first)
'1 => 2 => 3'

So, yeah it was much more difficult than I imagined. Now, excuse me, because I need a nap.

UPDATE Okay, I have a simpler recursive algorithm, but it takes two arguments.

def recursive_reverse2(prev, curr):
    if curr is None:
        return prev
    next = curr.next
    curr.next = prev
    return recursive_reverse2(curr, next)