Reverse a Linked List (Iterative) 🎯

Welcome to this comprehensive guide on reversing a linked list iteratively! In this lesson, we'll learn how to reverse a linked list using a step-by-step approach, making it easy for both beginners and intermediates to understand and apply this concept. Let's dive in!

Understanding Linked Lists 📝

A linked list is a linear data structure, composed of nodes where each node points to the next one. It's a common data structure used in computer science and is particularly useful when dealing with dynamic data.

markdown

Node: {
    data,
    next_node
}

data: The value stored in the node
next_node: A reference to the next node in the list

The Problem: Reverse a Linked List 💡

Given a linked list, write a function that reverses the list without using recursion.

Pseudo-code 📝

reverse_linked_list(head):
    prev = None
    current = head
    new_head = None

    while current is not None:
        next_node = current.next_node
        current.next_node = prev
        prev = current
        current = next_node

    if prev is not None:
        new_head = prev

    return new_head

Let's break down the pseudo-code above:

Initialize prev, current, and new_head to None.
In the while loop, we store the next node in next_node, reverse the link between the current node and the previous node, update prev and current accordingly.
When the current node reaches None, we have reached the end of the list, and prev now points to the new head of the reversed list.
Return the new head of the reversed list.

Implementation in Python 🎯

python

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

    def __repr__(self):
        return f"{self.data}"

def reverse_linked_list(head):
    prev = None
    current = head
    new_head = None

    while current is not None:
        next_node = current.next_node
        current.next_node = prev
        prev = current
        current = next_node

    if prev is not None:
        new_head = prev

    return new_head

# Creating a linked list
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

node1.next_node = node2
node2.next_node = node3
node3.next_node = node4

# Original Linked List
print("Original Linked List:")
print(node1, end=" -> ")
print(node2, end=" -> ")
print(node3, end=" -> ")
print(node4)

# Reversed Linked List
print("\nReversed Linked List:")
head = reverse_linked_list(node1)
while head is not None:
    print(head, end=" -> ")
    head = head.next_node

In this lesson, we've learned how to reverse a linked list iteratively. This skill will come in handy when dealing with dynamic data structures, especially in real-world projects. Keep practicing and happy coding! 🚀