Reverse a Linked List – Python (Step-by-Step)

🔁 Reverse a Linked List – Python (Step-by-Step)

Hi All,

Today I solved a fundamental problem in Data Structures: Reverse a Linked List.

📌 Problem Statement

Given the head of a singly linked list, reverse the list and return the new head.

🔍 Example

Input:

1 -> 2 -> 3 -> 4 -> 5

Output:

5 -> 4 -> 3 -> 2 -> 1

💡 Approach

🔹 Iterative Method (Optimal)

👉 We reverse the links one by one using pointers.

🧠 Step-by-Step Logic

We use three pointers:

prev → previous node
curr → current node
next_node → next node

Steps:

Initialize:
- prev = None
- curr = head
Traverse the list:
- Store next node
- Reverse link
- Move pointers forward

💻 Python Code

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


def reverseList(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

🔍 Dry Run

For:

1 -> 2 -> 3

Steps:

Reverse 1 → None
Reverse 2 → 1
Reverse 3 → 2 → 1

Final:

3 -> 2 -> 1

🖥️ Sample Output

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

⚡ Complexity Analysis

Time Complexity: O(n) ✅
Space Complexity: O(1) ✅

🧠 Alternative Method (Recursive)

def reverseList(head):
    if not head or not head.next:
        return head

    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None

    return new_head