Skip to content

Reversing a Linked List in Python: A Step-by-Step Coding Interview Guide

Updated: at 04:34 AM

Reversing a linked list is a common technical interview question asked to assess a candidate’s skills in data structures and algorithms using Python. Linked lists are fundamental data structures used extensively in Python programming for organizing data. Often, reversing a linked list becomes necessary to alter the natural order of elements during certain operations.

In this comprehensive guide, we will cover the following topics in Python:

Table of Contents

Open Table of Contents

Introduction to Linked Lists in Python

A linked list is a linear data structure consisting of nodes that are connected via pointers. Each node contains data and a pointer to the next node in the sequence. Linked lists are used to efficiently insert and remove elements from any position without reorganizing the entire structure.

In Python, each node can be implemented as a class containing the node’s value and a reference to the next node:

class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

To construct a linked list, we need to create a head node and subsequent nodes while linking them together by updating the next pointer:

# Construct linked list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

Some key operations on linked lists in Python include:

Next, we will explore various methods to reverse a linked list in Python.

Methods to Reverse a Singly Linked List

There are three main approaches to reversing a singly linked list in Python:

  1. Iterative Method
  2. Recursive Method
  3. Pointer Reversal Method

Let’s analyze each method with implementations, complexity analysis, pros and cons.

1. Iterative Method

The iterative method traverses the given linked list from head to tail, reversing pointers as it goes, finally returning the new head.

Algorithm:

  1. Initialize current, prev, and next pointers
  2. Iterate through list from head to tail
    1. Save next node as next
    2. Update next pointer of current to point to prev
    3. Shift prev and current one node forward
  3. Return prev as new head

Implementation:

def reverse_iterative(head):

  current = head
  prev = None

  while current:
    next = current.next
    current.next = prev
    prev = current
    current = next

  return prev

Time Complexity: O(N) Linear, where N is number of nodes

Space Complexity: O(1) Constant since only fixed pointers are used

Pros:

Cons:

2. Recursive Method

The recursive method reverses the linked list by recursively calling itself to switch node connections from tail to head.

Algorithm:

  1. Base case: Return when head is null
  2. Recursively call function on rest of list, advancing head
  3. Once stack unwinds, link returned nodes in reverse order

Implementation:

def reverse_recursive(head):

  if not head or not head.next:
    return head

  new_head = reverse_recursive(head.next)

  head.next.next = head
  head.next = None

  return new_head

Time Complexity: O(N) Linear, where N is number of nodes

Space Complexity: O(N) Linear due to recursive stack space

Pros:

Cons:

3. Pointer Reversal Method

The pointer reversal method iterates through the list while reversing the direction of every pointer.

Algorithm:

  1. Initialize current, prev, and next pointers
  2. Iterate through nodes reversing pointer direction
    1. Set next equal to current.next
    2. Point current.next to prev
    3. Shift prev and current one node forward
  3. Repeat process till all pointers reversed

Implementation:

def reverse_pointers(head):

  current = head
  prev = None

  while current:

    next = current.next
    current.next = prev
    prev = current
    current = next

  return prev

Time Complexity: O(N) Linear, where N is number of nodes

Space Complexity: O(1) Constant, only fixed pointers used

Pros:

Cons:

Now that we have covered the popular methods to reverse a linked list in Python along with analysis, let’s go through example implementations.

Step-by-Step Implementation and Code Examples

To solidify these concepts, we will walk through a step-by-step implementation of each method for reversing a sample linked list in Python.

Sample Linked List

First, let’s create a simple linked list to test our reverse functions:

class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

# Construct linked list
# 1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

1. Iterative Method

def reverse_iterative(head):

  current = head
  prev = None

  while current:
    next = current.next
    current.next = prev
    prev = current
    current = next

  return prev

reversed_head = reverse_iterative(head)

# Print reversed list
# 5 -> 4 -> 3 -> 2 -> 1
while reversed_head:
  print(reversed_head.value)
  reversed_head = reversed_head.next

Walkthrough:

  1. Initialize current as head, prev as null
  2. Save next node, reverse current.next pointer to prev
  3. Increment prev and current forward
  4. Return prev (new head) once current is null
  5. Print reversed linked list

2. Recursive Method

def reverse_recursive(head):

  if not head or not head.next:
    return head

  new_head = reverse_recursive(head.next)

  head.next.next = head
  head.next = None

  return new_head

reversed_head = reverse_recursive(head)

# Print reversed list
# 5 -> 4 -> 3 -> 2 -> 1
while reversed_head:
  print(reversed_head.value)
  reversed_head = reversed_head.next

Walkthrough:

  1. Base case returns if head is empty
  2. Recursively call on head.next to unwind stack
  3. Join returned nodes in reverse order
  4. Print reversed linked list

3. Pointer Reversal Method

def reverse_pointers(head):

  current = head
  prev = None

  while current:
    next = current.next
    current.next = prev
    prev = current
    current = next

  return prev

reverse_pointers(head)

# Print reversed original linked list
# 5 -> 4 -> 3 -> 2 -> 1
while head:
  print(head.value)
  head = head.next

Walkthrough:

  1. Initialize current and prev pointers
  2. Save next node, reverse current.next to prev
  3. Increment prev and current forward
  4. Repeat till all pointers reversed
  5. Original list now reversed in place

The step-by-step code examples illustrate how to implement linked list reversal in Python iteratively, recursively, and by pointer reversal.

Complexity Analysis

Analyzing time and space complexity is key to evaluating the efficiency of different algorithms. Let’s compare the complexities of the three linked list reversal methods:

AlgorithmTime ComplexitySpace Complexity
IterativeO(N) LinearO(1) Constant
RecursiveO(N) LinearO(N) Linear
Pointer ReversalO(N) LinearO(1) Constant

Observations:

For time efficiency, all three methods are comparable. For space efficiency, iterative or pointer reversal should be preferred over recursion.

Testing Reverse Functionality

Testing is vital to ensure our reverse functions work correctly on all inputs. Here are some example test cases:

Empty linked list - Reverse should handle empty list input

def test_empty_list(reverse_func):

  head = None
  reversed_head = reverse_func(head)

  assert reversed_head is None

Single node list - Reverse of 1 node is itself

def test_single_node(reverse_func):

  head = Node(1)
  reversed_head = reverse_func(head)

  assert reversed_head.value == 1
  assert reversed_head.next is None

General case - Reverse order should be as expected

def test_reverse_general(reverse_func):

  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)

  reversed_head = reverse_func(head)

  # Check values in reversed order
  assert reversed_head.value == 3
  assert reversed_head.next.value == 2
  assert reversed_head.next.next.value == 1

We test empty, single node, and general cases to verify correct behavior. Similarly, more test cases can be added for better coverage.

Applications of Reversing a Linked List

Some real-world applications where reversing a linked list becomes essential include:

Common examples are reversing order of entries in a scrollable feed, playlist, chat history or generating reverse timelines in apps. Linked list reversal serves as a fundamental building block in many such applications.

Common Mistakes and Tips for Beginners

Some common mistakes to avoid when reversing a linked list as a Python beginner:

Useful tips include:

Getting the pointer manipulation right is critical to correctly implementing linked list reversal in Python.

Conclusion

In this guide, we explored linked list data structures in Python and techniques to reverse a singly linked list iteratively, recursively and by pointer reversal. Detailed code examples, step-by-step walkthroughs, complexity analysis, testing and tips were covered to thoroughly explain list reversal approaches for technical interviews and coding challenges.

Linked list reversal serves as the foundation for more complex data structures like stacks, queues and doubly linked lists. Mastering basics like iterating nodes, manipulating pointers and handling edge cases pave the way for tackling advanced algorithms and real-world applications using Python.