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-by-Step Explanation

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

    return prev`

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

Conclusion

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.