In the world of algorithms, reversing a linked list is a classic problem that tests one's understanding of data structures and pointer manipulation. It's a common interview question and an essential skill for any programmer. We previously discussed the basics of a linked list; now let's turn things around, quite literally, and see how to reverse a linked list in Python.

What Does It Mean to Reverse a Linked List?

Reversing a linked list means that the head becomes the tail and vice versa. The direction of the pointers is inverted so that the element that was previously second is now second-to-last, and the last element now points to the element that was previously before it, and so on.

Algorithm to Reverse a Linked List

Input: Head of the linked list.

Output: Head of the reversed linked list.

1. Start with Initialization:

   • Set prev to None. This will become the new tail of the reversed list.

   • Set curr to head of the list. This is the current node we're looking to reverse.

   • Set next_node to None. This will temporarily hold the next node to visit.

2. Traverse the List:

   • While curr is not None (end of the linked list has not been reached):

     • Set next_node to curr.next (save the next node to move to after reversing).

     • Set curr.next to prev (reverse the pointer of the current node).

     • If prev is None, it means curr was the head and is now becoming the tail. Update linked_list.tail to curr.

     • Set prev to curr (move prev forward for the next reversal).

     • Set curr to next_node (proceed to the next node in the original list).

3. Finalize Reversal:

   • After the loop ends, curr will be None and prev will be at the last node that was processed, which is the new head.

   • Set linked_list.head to prev to mark the start of the reversed list.

4. Return the Reversed List:

   • The linked_list now points to the reversed linked list. Return linked_list.

End of Algorithm. This algorithm effectively reverses the linked list by reassigning the next pointers of each node to point to the previous node instead of the next one in the original list. The head and tail are then updated to reflect the reversed order.

Reversing a Linked List in Python: The Implementation

Let's look at the Python code that accomplishes this reversal:

from LinkedList import LinkedList, Node
def reverse(linked_list):
    prev = None    curr = linked_list.head
    next_node = None    while curr:
        next_node = curr.next        
        curr.next = prev
        if not prev:
            linked_list.tail = curr
        prev = curr
        curr = next_node

    linked_list.head = prev

    return linked_list

This function takes a LinkedList object and reverses it in-place. The prev pointer is used to keep track of the previous node, which becomes the next of the current node in the reversal process. The LinkedList class was implemented in previous blog post.

Putting Our Function to the Test

We can now test our reverse function:

if __name__ == "__main__":
    linked_list = LinkedList()
    linked_list.append(Node('A'))
    linked_list.append(Node('B'))
    linked_list.append(Node('C'))
    linked_list.append(Node('D'))

    print("Original List:")
    item = linked_list.head
    while item:
        print(f"Current Data: {item.data}")
        item = item.next    print(f'{"*" * 10} Reversing Linked List {"*" * 10}')
    reversed_list = reverse(linked_list)

    print("Reversed List:")
    item = reversed_list.head
    while item:
        print(f"Current Data: {item.data}")
        item = item.next

The output will demonstrate the linked list first in its original order and then in its reversed order, confirming the successful in-place reversal.

Conclusion

Reversing a linked list might seem daunting at first, but it's a logical process that becomes clear with practice. This operation is a stepping stone to more complex linked list manipulations and a better understanding of pointers and nodes.

Remember, the ability to reverse a linked list is not just for interviews; it's a skill that can come in handy in real-world scenarios, such as undo functionality in applications or reversing a route in navigation systems.

Next time you come across a linked list, try reversing it. It's a satisfying challenge that solidifies your data structure expertise. Happy coding!