Reverse Linked List DSA Solution - Pointer Reversal - Study Chapter | QuizMaker

Reverse Linked List explained with brute force, optimized pointer reversal, dry run, edge cases, complexity, and Python, C++, Java code.

Read
9m
Type
Chapter
Access
Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 5: Linked List

Learning Outcome

After this lesson, you should be able to reverse a linked list in-place while carefully preserving the next node before changing pointers.

Problem Statement

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

InputOutputWhy
1 -> 2 -> 3 -> 44 -> 3 -> 2 -> 1Every pointer direction is reversed.

Brute Force Approach

Copy all node values into an array, then rebuild a new linked list in reverse order.

This is easy to visualize, but it uses O(n) extra space and does not practice pointer manipulation.

Optimized Approach

Use three pointers: prev, curr, and nextNode. Save curr.next, point curr.next to prev, then move both pointers forward.

The key safety rule is to save the next node before changing curr.next.

Exact Pseudocode

prev = null
curr = head
while curr is not null:
  nextNode = curr.next
  curr.next = prev
  prev = curr
  curr = nextNode
return prev

Reference Code

class Solution:
    def reverseList(self, head):
        prev = None
        curr = head

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        return prev
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while (curr != nullptr) {
            ListNode* nextNode = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextNode;
        }

        return prev;
    }
};
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }

        return prev;
    }
}

Sample Dry Run

StepcurrnextNodeprev after reversal
Start1-null
Reverse 1121 -> null
Reverse 2232 -> 1 -> null
Reverse 3343 -> 2 -> 1 -> null
Finishnull-Return 4 -> 3 -> 2 -> 1

Complexity

MeasureValueReason
TimeO(n)Each node is visited once.
SpaceO(1)The reversal is in-place.

Edge Cases

Interview Checklist

FAQs

Why do we need three pointers?

prev builds the reversed part, curr is the node being processed, and nextNode preserves the remaining list.

Can this be done recursively?

Yes, but the iterative version is usually easier to explain and uses O(1) extra space.

What is the core pattern?

Pointer reversal.

Tags

Open on QuizMaker