How to reverse a linked list in Python

To reverse a linked list is a classic computer science problem. It tests your grasp of data structures and pointers. Python offers several elegant ways to solve this common interview question.

In this article, you will learn iterative and recursive techniques. You'll get practical tips, see real-world applications, and receive advice to debug your code to help you master this fundamental skill.

Basic iterative reversal with a while loop

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

def reverse_linked_list(head):
   prev, current = None, head
   while current:
       next_temp = current.next
       current.next = prev
       prev, current = current, next_temp
   return prev

# Example: reversing 1->2->3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
reversed_head = reverse_linked_list(head)
result = []
while reversed_head:
   result.append(reversed_head.data)
   reversed_head = reversed_head.next
print(result)--OUTPUT--[3, 2, 1]

The iterative approach in the reverse_linked_list function walks through the list, reversing each node's next pointer one by one. It cleverly uses two pointers, prev and current, to manage the reversal. The prev pointer starts as None because the original head of the list will become the new tail, which points to nothing.

Inside the while loop, the logic unfolds in a few key steps:

• A temporary variable, next_temp, stores the next node in the original sequence. This prevents you from losing the rest of the list when you reassign the pointer.
• The actual reversal happens when current.next is pointed backward to prev.
• Finally, you advance both pointers for the next iteration. prev becomes the current node, and current moves to the node saved in next_temp.

Once the loop completes, prev will be pointing to the new head of the fully reversed list.

Alternative reversal strategies

While the iterative loop is a workhorse for this problem, other techniques like recursion or using a stack offer different ways to think about the solution.

Recursive approach with head.next.next = head

def reverse_recursively(head):
   if not head or not head.next:
       return head
   new_head = reverse_recursively(head.next)
   head.next.next = head
   head.next = None
   return new_head

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
reversed_head = reverse_recursively(head)
result = []
while reversed_head:
   result.append(reversed_head.data)
   reversed_head = reversed_head.next
print(result)--OUTPUT--[3, 2, 1]

The recursive solution, reverse_recursively, elegantly flips the list by working its way to the end first. The function keeps calling itself until it reaches the last node. This final node is then returned up the call stack as the new_head of the reversed list.

As the recursion unwinds, the actual pointer reversal happens:

• The line head.next.next = head is the core of the logic. It makes the node that was originally *after* the current one point back to it.
• Then, head.next = None breaks the original forward link, which is crucial for preventing cycles.

This process continues until the original head becomes the new tail, pointing to None.

Using a stack for reversal

def reverse_with_stack(head):
   stack = []
   current = head
   while current:
       stack.append(current)
       current = current.next
   
   if not stack:
       return None
   
   new_head = stack.pop()
   current = new_head
   while stack:
       current.next = stack.pop()
       current = current.next
   current.next = None
   return new_head--OUTPUT--[3, 2, 1]

The reverse_with_stack function leverages a stack's Last-In, First-Out (LIFO) nature. It first traverses the entire linked list, pushing each node onto a stack. By the end, the stack holds all the nodes, with the original head at the bottom and the tail at the top.

• The reversal begins by popping the top node from the stack, which becomes the new_head.
• A loop then continues to pop nodes, linking each one to the next attribute of the previously popped node.
• Finally, the last node's next pointer is set to None to terminate the list.

Creating a LinkedList class with a reverse() method

class LinkedList:
   def __init__(self):
       self.head = None
   
   def append(self, data):
       new_node = Node(data)
       if not self.head:
           self.head = new_node
           return
       last = self.head
       while last.next:
           last = last.next
       last.next = new_node
   
   def reverse(self):
       prev, current = None, self.head
       while current:
           next_temp = current.next
           current.next = prev
           prev, current = current, next_temp
       self.head = prev

# Usage example
ll = LinkedList()
for i in range(1, 4):
   ll.append(i)
ll.reverse()
current, result = ll.head, []
while current:
   result.append(current.data)
   current = current.next
print(result)--OUTPUT--[3, 2, 1]

Wrapping the logic in a LinkedList class is a clean, object-oriented approach. It keeps the list's data and its operations, like append() and reverse(), neatly bundled together.

The reverse() method implements the same iterative logic you've already seen. The key distinctions are:

• It operates directly on the list instance's head.
• After the loop finishes, it reassigns self.head to the new first node, completing the in-place reversal.

Advanced reversal techniques

Building on those core strategies, you can tackle more complex problems, such as reversing a specific segment or using generators for a non-destructive reversed view.

Reversing a specific section with reverse_between()

def reverse_between(head, left, right):
   dummy = Node(0)
   dummy.next = head
   prev = dummy
   
   for _ in range(left - 1):
       prev = prev.next
   
   current = prev.next
   for _ in range(right - left):
       temp = current.next
       current.next = temp.next
       temp.next = prev.next
       prev.next = temp
   
   return dummy.next

# Example: reversing nodes 2-4 in list 1->2->3->4->5
head = Node(1)
current = head
for i in range(2, 6):
   current.next = Node(i)
   current = current.next
   
result = reverse_between(head, 2, 4)
values = []
while result:
   values.append(result.data)
   result = result.next
print(values)--OUTPUT--[1, 4, 3, 2, 5]

The reverse_between() function precisely flips a segment of the list from position left to right. It uses a dummy node to gracefully handle reversing from the list's head. The logic first locates the node just before the reversal section starts, which acts as an anchor. Then, for each node in the target segment, it performs a clever swap:

• It detaches the node from its current position.
• It re-inserts that node right after the anchor.

This process effectively pulls nodes from the segment one by one and prepends them to the start of the segment, reversing their order in place.

Utilizing generators for reversed traversal

def reverse_and_generate(head):
   # First reverse the list
   prev, current = None, head
   while current:
       next_temp = current.next
       current.next = prev
       prev, current = current, next_temp
   
   # Then yield values
   current = prev
   while current:
       yield current.data
       current = current.next

# Creating a list 1->2->3 and using the generator
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
print(list(reverse_and_generate(head)))--OUTPUT--[3, 2, 1]

The reverse_and_generate function offers a memory-efficient way to iterate through the list's values in reverse. It uses the yield keyword to create a generator, which produces values on demand rather than storing them all in a new list.

• First, the function reverses the entire linked list in place using the iterative method.
• After reversal, it traverses the newly ordered list, yielding each node's data one by one.

This makes it a great choice for very large lists where creating a second list just for the reversed data would be inefficient.

Functional programming with list conversions

def to_list(head):
   result = []
   current = head
   while current:
       result.append(current.data)
       current = current.next
   return result

def from_list(lst):
   dummy = Node(0)
   current = dummy
   for val in lst:
       current.next = Node(val)
       current = current.next
   return dummy.next

# Create a list and reverse it using slicing
head = from_list([1, 2, 3, 4, 5])
reversed_head = from_list(to_list(head)[::-1])
print(to_list(reversed_head))--OUTPUT--[5, 4, 3, 2, 1]

This functional approach sidesteps in-place pointer manipulation. Instead, it converts the linked list into a standard Python list, reverses it, and then builds a new linked list from the result. The process relies on two helper functions.

• The to_list() function traverses the original structure and stores its data in a Python list.
• Python’s powerful slice notation, [::-1], then creates a reversed copy of that list.
• Finally, from_list() takes this reversed list and constructs an entirely new linked list.

Move faster with Replit

Replit is an AI-powered development platform that transforms natural language into working applications. You can describe what you want to build, and Replit Agent creates it—complete with databases, APIs, and deployment.

For the linked list reversal techniques you've learned, Replit Agent can turn them into practical tools:

• Build a playlist feature that uses a stack-based reversal, like in reverse_with_stack, to create a "recently played" list in reverse chronological order.
• Create a text editor utility that implements reverse_between to flip the order of selected lines of text or code.
• Deploy a data processing pipeline that uses a generator, similar to reverse_and_generate, to efficiently analyze event logs from last to first.

Turn your own concepts from idea to application. Describe your app to Replit Agent, and it will write, test, and deploy the code for you.

Common errors and challenges

Reversing a linked list seems straightforward, but a few common pitfalls can trip you up, from losing track of your list to memory issues.

A frequent mistake is losing the reference to the new head of the list. After an in-place reversal, your original head variable now points to what has become the tail. If you try to traverse the list from that old variable, you'll only get the last node. You must remember to capture the new head returned by your function.

The reverse_with_stack() function introduces a potential memory problem. While conceptually simple, it has a hidden cost:

• It builds a stack that stores a reference to every node in the list. For a list with millions of items, this can consume a significant amount of memory.
• Though not a permanent memory leak, this O(n) space complexity is inefficient. The iterative approach, which uses constant space, is a much better choice for large datasets.

Finally, the reverse_between() function requires careful handling of edge cases. The use of a dummy node is a great technique for managing reversals that start at the head of the list. However, the real challenge is invalid input. The function as written doesn't check if left and right are within the list's bounds or if left is greater than right, which could cause your program to crash. A robust implementation needs to validate these inputs first.

Handling the "lost head" after printing a reversed list

A subtle but common error occurs when you traverse a reversed list just to print its contents. The variable you use to iterate through the list, such as reversed_head, ends up as None. If you try to use that same variable again, you'll find it's empty.

The code below demonstrates how this happens, leaving you with a "lost" list that you can no longer access from that variable.

# Reversing and printing immediately loses our reference
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

reversed_head = reverse_linked_list(head)
# After this loop, reversed_head will be None
while reversed_head:
   print(reversed_head.data)
   reversed_head = reversed_head.next

# Try to use the reversed list again
print("List values:", end=" ")  # This won't work as expected
while reversed_head:  # reversed_head is now None
   print(reversed_head.data, end=" ")
   reversed_head = reversed_head.next

The while loop consumes your reference by advancing the reversed_head pointer to the end of the list. When the loop finishes, the variable is None, leaving the list inaccessible. Here’s how to print the list while keeping its head reference intact.

# Store a reference to the head before traversing
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

reversed_head = reverse_linked_list(head)
# Save the head pointer before traversal
head_ref = reversed_head

# First traversal
while reversed_head:
   print(reversed_head.data)
   reversed_head = reversed_head.next

# We can still access the list through our saved reference
print("List values:", end=" ")
current = head_ref
while current:
   print(current.data, end=" ")
   current = current.next

The fix is straightforward: save a reference to the new head before you start iterating. By creating a separate variable, like head_ref, to hold the reversed_head, you keep the starting point safe. The while loop can then consume the original variable, which will end up as None. Your list remains fully accessible through head_ref for any later use. Keep an eye out for this whenever you traverse a data structure you need to reuse.

Fixing a memory leak in the reverse_with_stack() function

The reverse_with_stack() function can introduce a memory leak if you're not careful. The issue isn't the stack itself but a forgotten final step: terminating the list. Without it, the last node's next pointer creates an unintended cycle.

See if you can spot the missing line in the code below, which causes this problem.

def reverse_with_stack(head):
   stack = []
   current = head
   # This stores all nodes in memory but never clears the original links
   while current:
       stack.append(current)
       current = current.next
   
   if not stack:
       return None
   
   new_head = stack.pop()
   current = new_head
   while stack:
       current.next = stack.pop()
       current = current.next
   # Missing line to terminate the list
   return new_head

The new tail of the reversed list keeps its original next pointer, creating a cycle back into the list. This causes an infinite loop during traversal. See how the corrected implementation below prevents this.

def reverse_with_stack(head):
   if not head:
       return None
       
   stack = []
   current = head
   while current:
       stack.append(current)
       current = current.next
   
   new_head = stack.pop()
   current = new_head
   while stack:
       current.next = stack.pop()
       current = current.next
   # Important: terminate the list to prevent cycles
   current.next = None
   return new_head

The corrected reverse_with_stack() function fixes a critical bug where the new tail of the list kept its original next pointer, creating a cycle. This would cause an infinite loop during traversal. The solution is adding current.next = None after the loop finishes. This one line explicitly terminates the list, breaking the cycle. It's a crucial step to remember whenever you're manually re-linking nodes to form a new sequence.

Handling edge cases in reverse_between() function

The reverse_between() function is powerful but brittle. It assumes valid left and right inputs. If the range is outside the list's bounds, or if left is greater than right, the function will crash. Robust code must validate these inputs first.

The current implementation lacks these crucial checks. See if you can spot where the logic would fail if the list is shorter than expected or if a pointer unexpectedly becomes None.

def reverse_between(head, left, right):
   dummy = Node(0)
   dummy.next = head
   prev = dummy
   
   for _ in range(left - 1):
       prev = prev.next
       # No validation if prev becomes None
   
   current = prev.next
   for _ in range(right - left):
       temp = current.next
       # Will fail if temp is None (list shorter than expected)
       current.next = temp.next
       temp.next = prev.next
       prev.next = temp
   
   return dummy.next

The code doesn't account for a list that's shorter than the right index. The loops will advance pointers past the end of the list, causing a crash when trying to access None.next. The following code adds the required validation.

def reverse_between(head, left, right):
   # Handle invalid inputs
   if not head or left >= right or left < 1:
       return head
       
   dummy = Node(0)
   dummy.next = head
   prev = dummy
   
   # Navigate to position 'left'
   for _ in range(left - 1):
       if not prev.next:
           return head  # Not enough nodes
       prev = prev.next
   
   current = prev.next
   if not current:
       return head  # Not enough nodes
       
   # Reverse nodes between left and right
   for _ in range(right - left):
       if not current.next:
           break  # Not enough nodes
       temp = current.next
       current.next = temp.next
       temp.next = prev.next
       prev.next = temp
   
   return dummy.next

The corrected reverse_between() function adds crucial validation to prevent crashes. It now checks for invalid inputs, like left >= right, and ensures the list is long enough before proceeding. During the reversal loops, it verifies that pointers aren't None before accessing their next attribute. This makes the function robust against out-of-bounds errors. Always validate indices when working with subsections of data structures to avoid unexpected crashes from invalid user input or edge-case data.

Real-world applications

Once you've navigated the common pitfalls, you'll find that reversing a linked list is a key part of many software features.

Implementing a LIFO task stack with reverse_linked_list()

You can use the reverse_linked_list() function to quickly turn a chronological queue of tasks into a Last-In, First-Out (LIFO) stack, where the most recently added item is processed first.

def implement_task_stack(tasks):
   task_list = from_list(tasks)
   print(f"Original tasks: {to_list(task_list)}")
   
   # Convert to LIFO order using reversal
   stack = reverse_linked_list(task_list)
   print(f"Tasks as stack: {to_list(stack)}")
   
   # Process top two tasks
   print(f"Processing: {stack.data}")
   stack = stack.next
   print(f"Next up: {stack.data}")
   
   return stack

# Example usage
task_queue = ["Start server", "Initialize DB", "Load config", "Begin processing"]
implement_task_stack(task_queue)

The implement_task_stack function demonstrates a practical use for list reversal. It takes a list of tasks, initially in chronological order, and converts them into a linked list.

• By calling reverse_linked_list, it flips the entire sequence.
• This reordering means the most recently added task, "Begin processing," is now at the head of the list.

The function then simulates handling the first two tasks from this newly ordered list, showing how reversal can prioritize recent items.

Implementing undo functionality in a text editor

By reversing a chronological list of user actions, you can create an undo stack where the last operation performed is the first one to be undone.

def text_editor_with_undo(operations):
   # Record editing operations
   op_list = from_list(operations)
   print(f"Performed operations: {operations}")
   
   # Create undo stack by reversing operations
   undo_stack = reverse_linked_list(op_list)
   
   # Perform undo operations
   print("Undoing last 2 operations:")
   for _ in range(2):
       if undo_stack:
           print(f"  Undo: {undo_stack.data}")
           undo_stack = undo_stack.next
   
   # Remaining operations after undo
   remaining = to_list(undo_stack)
   print(f"Remaining operations to undo: {remaining}")

# Example with text editing operations
editor_actions = ["Insert paragraph", "Format text", "Add image", "Delete line"]
text_editor_with_undo(editor_actions)

The text_editor_with_undo function shows a practical application for list reversal. It takes a list of editing operations, which are recorded in the order they happen. By calling reverse_linked_list, it flips this entire sequence.

• This reordering places the most recent action, like "Delete line," at the very beginning of the new list.
• The code can then simply traverse this reversed list from the start to process "undo" requests in the correct order.

The example simulates this by handling the first two items from the newly created undo_stack.

Get started with Replit

Turn these concepts into a real tool. Describe your idea to Replit Agent, like “build a text utility to reverse selected lines” or “create a playlist app with a reverse chronological history feature.”

The agent writes the code, tests for errors, and deploys your application. Start building with Replit and bring your ideas to life.