The code given below will reverse a Linked List in place. In place means we won’t need additional space for reversing this list.
This will however destroy or modify our original list (so keep this in mind when you’re doing an in-place operation on a given input).
Ok so here’s the code to reverse a given Linked List:
class Node:
def __init__(self, data):
self.value = data
self.next = None
def reverse_list(head):
current = head
previous = None
nextnode = None
while current:
nextnode = current.next
current.next = previous
previous = current
current = nextnode
return previous
def print_list(head):
p = head
while p:
print(p.value)
p = p.next
# testing
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
print_list(a)
newhead = reverse_list(a)
print('after reversing: ')
print_list(newhead)
# output
# 1
# 2
# 3
# after reversing:
# 3
# 2
# 1
The trick here is to maintain three pointers: current, previous, nextnode
And the process can be visualized on paper as follows:
That’s all in this post. Thanks for reading! 🙂
CS Mumbai 