Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

linkedlist
python
operations
data structures

How to reverse a linked list in Python

Educative Answers Team

Linked List in Python

Given below is the implementation of a standard class-based singly Linked List in Python.

# A single node of a singly Linked List
class Node:
  # constructor
  def __init__(self, data = None, next=None): 
    self.data = data
    self.next = next

# A Linked List class with a single head node
class LinkedList:
  def __init__(self):  
    self.head = None
  
  # insertion method for the 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 method for the linked list
  def printLL(self):
    current = self.head
    while(current):
      print(current.data)
      current = current.next

# Singly Linked List with insertion and print methods
LL = LinkedList()
LL.insert(3)
LL.insert(4)
LL.insert(5)
LL.printLL()
Implementation of a singly linked list in Python

Reversing a linked list

Now that we have the implementation of a Linked List in Python, we want to implement a method reverse() which does the following:

  • All the links start pointing in the opposite direction.
  • The head starts pointing to the last element of the list.
svg viewer
Reversing a Linked List

Given below is an iterative approach as to how you can reverse a given Linked List in Python:

  • Initialize variables:
    • previous: Initially pointing at None (line 3), this variable points to the previous element so the node.next link can be reversed using it (line 9). This is then updated to the node next to it, i.e., current (line 10).

    • current: Initially pointing to head (line 4), the node being pointed to by this variable gets its node.next set to the previous item in the list (line 9). This is then updated to the node next to it,​ i.e., following (line 11).

    • following: Initially pointing to the second node (line 5), this is used so the current pointer may move one step ahead (line 12-13) in each iteration.

def reverseList(list):
  # initialize variables
  previous = None         # `previous` initially points to None
  current = list.head     # `current` points at the first element
  following = current.next    # `following` points at the second element

  # go till the last element of the list
  while current:
      current.next = previous # reverse the link
      previous = current      # move `previous` one step ahead
      current = following         # move `current` one step ahead
      if following:               # if this was not the last element
          following = following.next    # move `following` one step ahead

  list.head = previous


# Testing
LL = LinkedList()
LL.insert(1)
LL.insert(2)
LL.insert(3)
LL.insert(4)
print("Linked List")
LL.printLL()
print("Reversed Linked List")
reverseList(LL)
LL.printLL()

RELATED TAGS

linkedlist
python
operations
data structures
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring