ASSIGNMENT 22

1.Reverse a Linked List

Problem

Given the head of a singly linked list, reverse the list so that the direction of all pointers is changed.

Example

Input:
1 → 2 → 3 → 4 → 5

Output:
5 → 4 → 3 → 2 → 1

Approach Used

Iterative Approach (Most Efficient)

This method uses three pointers to reverse the direction of the linked list step by step.
•One pointer keeps track of the previous node
•One pointer represents the current node
•One pointer stores the next node

The main idea is to reverse the link of each node so that it points to the previous node instead of the next one.

Step 1: Initialize Pointers

Start with two pointers:
• Previous pointer is set to null
• Current pointer is set to the head of the list

Step 2: Traverse the List

Move through the linked list until you reach the end.

Step 3: Store the Next Node

Before changing any links, store the next node of the current node.
This ensures the remaining list is not lost.

Step 4: Reverse the Link

Change the direction of the current node so that it points to the previous node instead of the next node.

Step 5: Move the Pointers Forward

Move the previous pointer to the current node.
Move the current pointer to the next node (which was stored earlier).

Step 6: Repeat the Process

Continue these steps until the current pointer becomes null.
This means the entire list has been reversed.

Step 7: Update Head

At the end of the process, the previous pointer will be pointing to the new head of the reversed list.

`class Solution:
def reverseList(self, head):
prev = None
curr = head

while curr:
    next_node = curr.next   # store next
    curr.next = prev        # reverse link
    prev = curr             # move prev
    curr = next_node        # move curr

Complexity Analysis
•Time Complexity: O(n) → each node is visited once
•Space Complexity: O(1) → no extra memory is used

• Reversing a linked list is a fundamental problem that focuses on pointer manipulation. By changing the direction of links one by one, we can completely reverse the list in a single traversal.