Introduction:

Linked lists are a fundamental data structure in computer science, offering efficient insertion and deletion operations. However, when it comes to manipulating the order of elements within a linked list, a common task is reversing the list. In this article, we will explore the process of reversing a linked list, starting with a naive brute-force approach and gradually unveiling the most optimal solution. We will delve into the intricacies of each step of the code, providing clear explanations to ensure a comprehensive understanding of the process.

Naive Brute-Force Approach:

To comprehend the optimal solution, it is essential to first explore the naive brute-force approach. The brute-force method involves iterating through the linked list and altering the pointers to reverse the order of elements. Let's take a closer look at the steps involved:

Traverse the linked list iteratively, keeping track of the current, previous, and next nodes.
At each iteration, update the next pointer of the current node to point to the previous node.
Move the previous and current pointers one step forward in the list.
Repeat steps 2 and 3 until the end of the linked list is reached.
Finally, update the head pointer of the list to point to the last node encountered during the traversal.

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


def reverseList(head):
    if head is None or head.next is None:
        return head

    current = head
    previous = None
    next_node = None

    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    head = previous
    return head

While this approach achieves the desired result, it has a time complexity of O(n) since it requires iterating through the entire linked list. Additionally, it requires maintaining multiple pointers, increasing the complexity of the code.

The Optimal Solution:

To optimize the process of reversing a linked list, we can employ a recursive approach. This elegant solution reduces the complexity and improves code readability.

Recursion:

Let's break down the steps involved:

Define a recursive function, let's call it reverseList, that takes a node as input.
Check if the current node or the next node is None, indicating the end of the list. If so, return the current node.
Recursively call the reverseList function with the next node as the argument.
Update the next node's next pointer to point back to the current node, effectively reversing the direction.
Set the current node's next pointer to None, breaking the link to the next node.
Return the reversed list starting from the last node encountered in the recursion.

By utilizing the power of recursion, this optimal solution achieves a time complexity of O(n) while maintaining simplicity and readability in the code. The recursive nature of the solution elegantly handles the reversal process.

Code Implementation: Now, let's provide a code implementation to solidify the understanding of the optimal solution:

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


def reverseList(node):
    if node is None or node.next is None:
        return node

    reversed_list = reverseList(node.next)
    node.next.next = node
    node.next = None

    return reversed_list

In this code snippet, we define a Node class to represent individual nodes of the linked list. The reverseList function takes a node as input and performs the reversal recursively. The base case checks if the node or the next node is None, signaling the end of the list. If so, it returns the current node. Otherwise, it recursively calls reverseList with the next node and updates the pointers accordingly.

One Pointers Approach (Iterative Approach):

The reverseList function takes the head node of a singly-linked list as input and returns the head node of the reversed list.
The variable dummy is initialized as None. This will be used to store the reversed list.
The while loop is used to traverse the original list. The loop continues until the head node becomes None, indicating the end of the original list.
Inside the loop, the next1 variable is used to store the reference to the next node. This is necessary because we will be modifying the head.next pointer, and we need to save the reference to the next node before the modification.
The head.next pointer is then updated to point to the dummy node, effectively reversing the direction of the pointer. This connects the current node to the reversed list.
The dummy node is updated to become the current head node, as it will become the new head of the reversed list.
Finally, the head node is updated to the saved next1 node, moving to the next node in the original list for the next iteration.
Once the while loop finishes, the dummy node will be the head of the reversed list, so we return it.

# Definition for singly-linked list.
 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = None
        while head != None:
            next1 = head.next
            head.next = dummy
            dummy = head
            head = next1
        return dummy

Conclusion:

Reversing a linked list is a common task that requires careful consideration of efficiency and code complexity. While a brute-force approach exists, the optimal solution utilizes the power of recursion to achieve a more efficient and elegant solution.

By following the steps outlined in this article, you can confidently implement the optimal solution to reverse a linked list. Remember to choose the right approach based on the specific requirements of your project, considering factors such as time complexity, code readability, and maintainability.

Happy Coding ✨

Balaji.dev