Reverse a Linked List (Iterative and Recursive Approach)

Nidhi Sharma
9h
2.3k
0
0

Article

Introduction

The Reverse a Linked List problem is one of the most common DSA interview questions related to linked lists. Interviewers ask this question to test your understanding of pointer manipulation, traversal order, and recursion.

In simple terms, this problem asks you to reverse the direction of links in a linked list so that the last node becomes the first.

What Does It Mean to Reverse a Linked List?

In a linked list, each node points to the next node.

Reversing a linked list means:

Changing each node’s next pointer
Making it point to the previous node instead of the next

Example

Original list:

1 → 2 → 3 → 4 → 5 → null

Reversed list:

5 → 4 → 3 → 2 → 1 → null

Why Brute Force Approach Is Not Ideal

A naive approach could be:

Store all node values in an array
Reverse the array
Rebuild the linked list

Problems with This Approach

Extra space is required
Node links are not handled directly

Interviewers expect a pointer-based solution.

Iterative Approach (Most Common in Interviews)

The iterative approach is the most popular and easiest to understand method.

Key Idea

We use three pointers:

prev – points to the previous node
current – points to the current node
next – temporarily stores the next node

We reverse the link step by step while moving forward.

Step-by-Step Iterative Explanation

Steps:

Initialize prev as null
Set current as head
While current is not null:
- Save current.next in next
- Point current.next to prev
- Move prev to current
- Move current to next
At the end, prev becomes the new head

Iterative Dry Run Example

Linked List:

1 → 2 → 3 → null

Step	prev	current	next
Start	null	1	2
1	1	2	3
2	2	3	null
End	3	null	-

Reversed List:

3 → 2 → 1 → null

Iterative Code Implementation

C++ Code

ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* current = head;

    while (current != NULL) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Java Code

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Python Code

def reverseList(head):
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

Recursive Approach (Conceptual and Important)

The recursive approach uses the call stack to reverse the list.

Key Idea

Reverse the rest of the list
Fix the current node at the end

This approach is elegant but slightly harder to understand.

Step-by-Step Recursive Explanation

Steps:

If list is empty or has one node, return it
Recursively reverse the rest of the list
Fix the current node’s pointer
Return the new head

Recursive Code Implementation

C++ Code

ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;

    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;

    return newHead;
}

Java Code

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;

    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return newHead;
}

Python Code

def reverseList(head):
    if head is None or head.next is None:
        return head

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

    return new_head

Iterative vs Recursive Comparison

Feature	Iterative	Recursive
Space Usage	O(1)	O(n)
Complexity	Simple	Slightly complex
Interview Preference	High	Medium

Time and Space Complexity

Time Complexity: O(n)
Space Complexity:
- Iterative: O(1)
- Recursive: O(n) (recursion stack)

Important Edge Cases

Empty linked list
Single node linked list
Linked list with two nodes

These cases are often tested in interviews.

Common Interview Follow-Up Questions

Reverse a linked list in groups
Reverse only part of a linked list
Reverse doubly linked list

Understanding basic reversal helps solve these.

Summary

The Reverse a Linked List problem is a fundamental linked list question that tests pointer manipulation skills. The iterative approach is space-efficient and preferred in interviews, while the recursive approach helps build conceptual understanding. Mastering both methods is essential for solving many advanced linked list problems confidently in technical interviews.