Reversing a singly linked list is a fundamental problem in computer science and forms a part of many coding interviews. In this blog post, we'll delve into the steps involved in reversing a singly linked list using Python. We'll also discuss the provided code snippet, explain each step, and analyze its time and space complexity.

Understanding the Problem:

Given the head of a singly linked list, our task is to reverse the list and return the reversed version. For example, if the input linked list is [1, 2, 3, 4, 5], the reversed list should be [5, 4, 3, 2, 1].

Approach:

We'll utilize a simple iterative approach to reverse the linked list. The idea is to traverse the list while maintaining three pointers: prev, curr, and nextNode.

Explanation of the Code:

Let's break down the provided Python code snippet:

# 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]:
        prev, curr = None, head
        while curr:
            nextNode = curr.next  # Store the next node
            curr.next = prev       # Reverse the pointer
            prev = curr            # Move prev to curr
            curr = nextNode        # Move curr to the next node
        return prev

We define a class Solution with a method reverseList, which takes the head of the linked list as input and returns the reversed list.

• Initially, we set prev to None and curr to the head of the linked list.
• We enter a while loop that iterates until curr becomes None, indicating the end of the list.
• Inside the loop, we store the next node of curr in nextNode.
• We then reverse the link of curr by pointing its next to prev.
• After reversing the link, we move prev to curr and curr to nextNode, progressing to the next nodes.
• Once the loop ends, prev points to the new head of the reversed list, so we return prev.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because we traverse the entire list once.

Space Complexity:

The space complexity is O(1) since we use a constant amount of extra space regardless of the input size. We only use a few extra pointers to keep track of the nodes being processed.

Conclusion:

Reversing a singly linked list is a common problem in coding interviews and real-world applications. By understanding the iterative approach and the provided code snippet, you can effectively tackle this problem. The time and space complexities of the solution demonstrate its efficiency, making it a practical solution for reversing linked lists in Python.

Happy coding!