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
tail and you’re ok with going backwards with
next and vice versa.
The sane and obvious way is to use three pointers (
front); you make the
middle point to
back, and shift everything one step right until
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