How to Reverse a Linked List in Python

It’s important to know about data types and one that comes up fairly regularly is that of Linked Lists.

Let’s write the following base code to create a Linked List.

# Defintion of a single Node
class Node:
  # takes input data and next node
  def __init__(self, data = None, next=None): 
    self.data = data
    self.next = next

# Definition of a Linked List
class LinkedList:
  def __init__(self):  
    self.head = None
  
  # Insert a node into our Linked List
  def insert(self, data):
    newNode = Node(data)
    if(self.head):
      current = self.head
      while(current.next):
        current = current.next
      current.next = newNode
    else:
      self.head = newNode
  
  # Print our Linked List so we can see how it looks
  def render(self):
    current = self.head
    while(current):
      print(current.data)
      current = current.next

Now that we have a base class, let’s insert a couple of nodes and print it out to see what we are working with:

# Define our LinkedList
ll = LinkedList()

# Insert a couple of nodes
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.insert(4)

# Render it out to the screen
ll.render()

What do we need to do to reverse this linked list?

Let’s start by creating a reverse function.

We should know that:

• All the links start pointing in the opposite direction
• The head starts to point to the last element of the list

Using an iterative approach, let’s start writing our function.

We will need to create a couple of variables to keep track of the position of each of our nodes as we loop through.

Some things to note:

previous initially points to None. This becomes the head on consecutive calls.

current points to the first element. This is the current head element point.

following points to the second element. This is the next element point.

# takes a `list` input
def reverse(list):

  # initialize our 3 main variables
  previous = None
  current = list.head
  following = current.next

  # keep looping until at the end of the list
  while current:
    
    # reverse the link
    current.next = previous
    previous = current
    current = following

    # if there are more nodes and this isn't the end
    if following:
      following = following.next

  # set the head to the previous item
  list.head = previous

Let’s test it!

# Define a LinkedList
ll = LinkedList()

# Insert some nodes
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.insert(4)

# Render our list in it's current order
print("Linked List")
ll.render()

# Reverse the list
reverse(ll)

# Render our list in it's new order
print("Reversed Linked List")
ll.render()

You know know how to reverse a list in Python!