Reverse a Linked List

In this task, I worked on reversing a singly linked list.

Given the head of a linked list, the goal is to reverse the direction of all the nodes and return the new head.

What I Did

I created a function reverseList that:

• Takes the head of a linked list


• Reverses the links between nodes


• Returns the new head of the reversed list

How I Solved It

Instead of creating a new list , I reversed the list in-place using an iterative approach.

Approach

I used three pointers:

• 
  prev → keeps track of the previous node (initially None)


• 
  curr → points to the current node


• 
  next_node → temporarily stores the next node

Logic Behind It

At each step:

1. Store the next node → next_node = curr.next
   


2. Reverse the link → curr.next = prev
   


3. Move prev forward → prev = curr
   


4. Move curr forward → curr = next_node
   

Repeat this until curr becomes None.

Code

class ListNode:

    def __init__(self, val=0, next=None):

        self.val = val

        self.next = next



def reverseList(head):

    prev = None

    curr = head



    while curr:

        next_node = curr.next   

        curr.next = prev        

        prev = curr             

        curr = next_node        



    return prev

How It Works

The algorithm walks through the list once and flips the direction of each link.

• The original head becomes the last node


• The last node becomes the new head

By the end, prev will be pointing to the new head of the reversed list.

Time Complexity

• 
  O(n) → traverse the list once

Space Complexity

• 
  O(1) → no extra space used

Example

Original:

1 → 2 → 3 → 4 → None

Reversed:

4 → 3 → 2 → 1 → None