CA 22 - Reverse a Linked List

Problem

Given the head of a linked list, the task is to reverse the list and return the new head.

Output

Example 1
Output: 5 -> 4 -> 3 -> 2 -> 1

My Approach

To solve this problem, I used the iterative method.

I maintain three pointers:

prev to store the previous node
curr to store the current node
next to store the next node

I iterate through the linked list:

First, I store the next node
Then I reverse the link by pointing the current node to the previous node
Then I move all pointers one step forward

I repeat this until the list is fully reversed.

This works because we change the direction of links step by step without losing track of the remaining nodes. ()

This approach is efficient because:

It requires one traversal
It uses constant extra space
Code

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev