# Reversing a Linked List: the sane way, the recursive way and the push way

Reversing a SLL takes O(N). You can reverse a doubly linked list in O(1) if you swap head and tail and you’re ok with going backwards with next and vice versa.

The sane and obvious way is to use three pointers (back, middle and front); you make the middle point to back, and shift everything one step right until front is None.

def bmfReverse(self):
back = None
front = middle.next

while True:
middle.next = back
if front is None: break
back = middle
middle = front
front = front.next



It is easy to turn this into a recursive function.

def recBmf(self, back=None, middle=None, front=None):
# setup
if middle is None: middle = self.head
if front is None: front = middle.next

middle.next = back

# base case
if front is None:
return
return self.recBmf(middle, front, front.next)


Finally, that’s the push-reverse strategy. It’s fucked up weird to read, but the idea is actually pretty simple: you keep pushing the front node (current) on the new result list, and as a last step you update the head pointer. Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

def pushReverse(self):
result = None

while current is not None:
# save the next node
next = current.next

# move the node onto result
current.next = result
result = current

# update current
current = next


def reverse(self):