Reverse a linked list in Python

Reverse a linked list in Python

I'm happy to respond in English for you.

Reversing a linked list is a fundamental problem in computer science, and it has many practical applications, such as when implementing algorithms like sorting or searching data structures. In this response, I'll show you how to reverse a linked list using Python.

What is a Linked List?

Before we dive into the solution, let's briefly explain what a linked list is. A linked list is a linear collection of elements called nodes, where each node points to the next node in the sequence through a reference (i.e., a "link" or a "pointer"). This allows for efficient insertion and deletion of nodes at any position in the list.

Reversing a Linked List

To reverse a linked list, we can use a simple iterative approach. Here's the step-by-step process:

Here's the Python code for reversing a linked list:

class Node:
def init(self, data):
self.data = data
self.next = None
def reverse_linked_list(head):
prev = None
curr = head
next_node = None
while curr is not None:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
Example usage
head = Node(1)
second_node = Node(2)
third_node = Node(3)
head.next = second_node
second_node.next = third_node
print("Original list:")
while head is not None:
print(head.data, end=" ")
head = head.next
print()
reversed_head = reverse_linked_list(head)
print("nReversed list:")
while reversed_head is not None:
print(reversed_head.data, end=" ")
reversed_head = reversed_head.next
print()

In this code:

Time Complexity

The time complexity for reversing a linked list using this approach is O(n), where n is the number of nodes in the list. This is because we only visit each node once, updating its next pointer accordingly.

Space Complexity

The space complexity is O(1), since we only need to keep track of three variables (prev, curr, and next_node) during the reversal process. These variables occupy a constant amount of space regardless of the size of the input list.

In conclusion, reversing a linked list can be achieved using an iterative approach in Python. By looping through the list and updating each node's next pointer, we can efficiently reverse the order of nodes in the linked list.

How to iterate a linked list in Python?

I'd be happy to help you with that!

In Python, there are several ways to iterate over a linked list. Here are a few common methods:

class Node:
def init(self, value):
self.value = value
self.next = None
def print_list(head):
if head is None:
return
print(head.value)
print_list(head.next)
Example usage:
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3
print_list(node1)  # Output: 1, 2, 3

However, recursive functions can be less efficient and may cause a stack overflow for large lists.

class Node:
def init(self, value):
self.value = value
self.next = None
def print_list(head):
current = head
while current is not None:
print(current.value)
current = current.next
Example usage:
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3
print_list(node1)  # Output: 1, 2, 3

This method is more efficient and easier to understand.

class Node:
def init(self, value):
self.value = value
self.next = None
def print_list(head):
current = head
while current is not None:
yield current.value
current = current.next
Example usage:
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3
for value in print_list(node1):
print(value)  # Output: 1, 2, 3

This method is useful when you need to process the values in the linked list one by one.

In conclusion, iterating over a linked list in Python can be done using recursive functions, iterative loops, or generator functions. The choice of method depends on your specific use case and personal preference.