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
    middle = self.head
    front = middle.next

    while True:
        middle.next = back
        if front is None: break
        # advance the three pointers
        back = middle
        middle = front
        front = front.next

    self.head = middle

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: 
        self.head = middle
        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
    current = self.head
        
    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

    self.head = result

Bonus: reversing a doubly linked list

Oh Python, it’s not even fun this way!

def reverse(self):
    n = self.head
    while n is not None:
        n.next, n.prev = n.prev, n.next
        n = n.prev
    self.head, self.tail = self.tail, self.head