Reverse Linked List

🎯

Reverse Linked List

easyLINKED_LISTAmazonFacebookMicrosoft

Imagine you have a train of connected carriages and you want to reverse their order without detaching them all at once. This problem is about reversing the order of nodes in a linked list in-place.

💡 Reversing a linked list is a fundamental problem that teaches how to manipulate pointers or references in a linked list. Beginners often struggle because it requires careful handling of node connections to avoid losing parts of the list.

📋

Problem Statement

Given the head of a singly linked list, reverse the list and return the reversed list's head.

The number of nodes in the list is in the range [1, 10^5].Node values can be any integer.You must reverse the list in-place with O(1) extra memory.

💡

Example

Input"head = [1, 2, 3, 4, 5]"

Output[5, 4, 3, 2, 1]

Starting from 1->2->3->4->5, after reversal the list becomes 5->4->3->2->1.

• Single node list → output is the same single node
• Two node list → nodes swapped
• List with all nodes having the same value → reversed list looks identical but pointers reversed
• Very large list (e.g., 10^5 nodes) → must not cause stack overflow or timeout

⚠️

Common Mistakes

Not saving next node before reversing pointer

Loses the rest of the list, resulting in incomplete reversal or null pointer errors

✅ Always save next node before changing current's next pointer

Forgetting to set head.next to null in recursive approach

Creates a cycle in the list, causing infinite loops or stack overflow

✅ Explicitly set head.next = None/null after reversing pointers

Using recursion on very large lists without tail recursion optimization

Stack overflow error due to deep recursion

✅ Prefer iterative approach or tail-recursive helper function if language supports optimization

Not handling empty or single-node list as base case

Code may crash or behave unexpectedly on minimal inputs

✅ Add base case checks for null or single node at start

Confusing previous and next pointers during reversal

Pointers may point incorrectly, causing corrupted list

✅ Carefully track and update pointers step-by-step, using temporary variables

🧠

Brute Force (Recursive Reversal)

💡 This approach uses recursion to reverse the list by reaching the end and then rewiring pointers on the way back. It helps beginners understand the problem by thinking about the list from the end backwards.

Intuition

Recursively reverse the rest of the list after the head, then put the head at the end of the reversed list.

Algorithm

1. If the list is empty or has one node, return it as is.
2. Recursively reverse the sublist starting from the second node.
3. Make the next node point back to the head.
4. Set the head's next pointer to null to avoid cycles.
5. Return the new head of the reversed list.

💡 The recursion unwinds from the tail, rewiring pointers step-by-step, which can be tricky to visualize at first.

</>

Code

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

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

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->2->3->4->5
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = reverseList(head)
    # Print reversed list
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

if not head or not head.next:Base case: if list is empty or single node, it's already reversed

p = reverseList(head.next)Recursively reverse the sublist after head

head.next.next = headMake the next node point back to current head, reversing the link

head.next = NoneSet current head's next to None to avoid cycle

return pReturn new head of reversed list from recursion

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution sol = new Solution();
        ListNode newHead = sol.reverseList(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

if (head == null || head.next == null) return head;Base case: empty or single node list is reversed as is

ListNode p = reverseList(head.next);Recursively reverse the sublist after head

head.next.next = head;Reverse the pointer of the next node to point back to head

head.next = null;Break the original link to avoid cycle

return p;Return new head of reversed list

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    Solution sol;
    ListNode* newHead = sol.reverseList(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

if (!head || !head->next) return head;Base case: empty or single node list is reversed as is

ListNode* p = reverseList(head->next);Recursively reverse the sublist after head

head->next->next = head;Reverse the pointer of the next node to point back to head

head->next = nullptr;Break the original link to avoid cycle

return p;Return new head of reversed list

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseList(head) {
    if (!head || !head.next) return head;
    let p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

// Driver code
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const newHead = reverseList(head);
let curr = newHead;
let output = '';
while (curr) {
    output += curr.val + ' ';
    curr = curr.next;
}
console.log(output.trim());

Line Notes

if (!head || !head.next) return head;Base case: empty or single node list is reversed as is

let p = reverseList(head.next);Recursively reverse the sublist after head

head.next.next = head;Reverse the pointer of the next node to point back to head

head.next = null;Break the original link to avoid cycle

return p;Return new head of reversed list

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, but recursion uses call stack proportional to n

💡 For n=20, this means 20 function calls stacked, which is manageable but can cause stack overflow for very large n

Interview Verdict: Accepted but not optimal due to recursion stack

This approach works but risks stack overflow on large inputs; good for understanding recursion but not always practical.

🧠

Iterative Reversal Using Three Pointers

💡 This approach iteratively reverses the list by moving through it once and rewiring pointers on the fly. It is the most common and efficient method used in interviews.

Intuition

Use three pointers: previous, current, and next to reverse the direction of each link as you traverse the list.

Algorithm

1. Initialize previous pointer as null and current pointer as head.
2. Iterate while current is not null:
3. Save next node.
4. Reverse current's next pointer to previous.
5. Move previous to current and current to next.
6. Return previous as the new head.

💡 The key is carefully saving the next node before changing pointers to avoid losing the rest of the list.

</>

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_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = reverseList(head)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

prev = NoneInitialize previous pointer to null because new tail will point to null

curr = headStart current pointer at head to begin traversal

next_temp = curr.nextSave next node before changing current's next pointer

curr.next = prevReverse current node's pointer to previous node

prev = currMove previous pointer forward to current node

curr = next_tempAdvance current pointer to next node

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution sol = new Solution();
        ListNode newHead = sol.reverseList(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode prev = null;Previous pointer starts as null for new tail

ListNode curr = head;Current pointer starts at head for traversal

ListNode nextTemp = curr.next;Save next node before reversing pointer

curr.next = prev;Reverse current node's pointer to previous node

prev = curr;Move previous pointer forward

curr = nextTemp;Advance current pointer

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    Solution sol;
    ListNode* newHead = sol.reverseList(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode* prev = nullptr;Previous pointer starts as null for new tail

ListNode* curr = head;Current pointer starts at head for traversal

ListNode* nextTemp = curr->next;Save next node before reversing pointer

curr->next = prev;Reverse current node's pointer to previous node

prev = curr;Move previous pointer forward

curr = nextTemp;Advance current pointer

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

// Driver code
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const newHead = reverseList(head);
let curr = newHead;
let output = '';
while (curr) {
    output += curr.val + ' ';
    curr = curr.next;
}
console.log(output.trim());

Line Notes

let prev = null;Previous pointer starts as null for new tail

let curr = head;Current pointer starts at head for traversal

let nextTemp = curr.next;Save next node before reversing pointer

curr.next = prev;Reverse current node's pointer to previous node

prev = curr;Move previous pointer forward

curr = nextTemp;Advance current pointer

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited once and pointers are reversed in-place without extra memory

💡 For n=20, this means 20 pointer changes and no extra memory, making it very efficient.

Interview Verdict: Accepted and optimal for interviews

This is the preferred approach in interviews due to its clarity, efficiency, and no risk of stack overflow.

🧠

Recursive Reversal with Helper Function (Tail Recursion Style)

💡 This approach uses a helper function with extra parameters to carry previous and current nodes, simulating iteration with recursion. It helps understand how recursion can mimic iteration.

Intuition

Pass previous and current nodes as parameters, reverse current's pointer to previous, and recurse forward until the end.

Algorithm

1. Define a helper function that takes previous and current nodes.
2. If current is null, return previous as new head.
3. Save next node.
4. Reverse current's next pointer to previous.
5. Recurse with current as previous and next as current.
6. Call helper with null and head initially.

💡 This approach is a recursive version of the iterative method, making the pointer changes explicit in recursion parameters.

</>

Code

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

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        next_temp = curr.next
        curr.next = prev
        return helper(curr, next_temp)
    return helper(None, head)

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = reverseList(head)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

def helper(prev, curr):Helper function carries previous and current nodes for recursion

if not curr:Base case: reached end of list, return previous as new head

next_temp = curr.nextSave next node before reversing pointer

curr.next = prevReverse current node's pointer to previous

return helper(curr, next_temp)Recurse forward with updated pointers

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        return helper(null, head);
    }

    private ListNode helper(ListNode prev, ListNode curr) {
        if (curr == null) return prev;
        ListNode nextTemp = curr.next;
        curr.next = prev;
        return helper(curr, nextTemp);
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution sol = new Solution();
        ListNode newHead = sol.reverseList(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

return helper(null, head);Start recursion with previous null and current head

if (curr == null) return prev;Base case: end of list reached, return previous as new head

ListNode nextTemp = curr.next;Save next node before reversing pointer

curr.next = prev;Reverse current node's pointer to previous

return helper(curr, nextTemp);Recurse forward with updated pointers

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* helper(ListNode* prev, ListNode* curr) {
        if (!curr) return prev;
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        return helper(curr, nextTemp);
    }

    ListNode* reverseList(ListNode* head) {
        return helper(nullptr, head);
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    Solution sol;
    ListNode* newHead = sol.reverseList(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

if (!curr) return prev;Base case: end of list reached, return previous as new head

ListNode* nextTemp = curr->next;Save next node before reversing pointer

curr->next = prev;Reverse current node's pointer to previous

return helper(curr, nextTemp);Recurse forward with updated pointers

return helper(nullptr, head);Start recursion with previous null and current head

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseList(head) {
    function helper(prev, curr) {
        if (!curr) return prev;
        let nextTemp = curr.next;
        curr.next = prev;
        return helper(curr, nextTemp);
    }
    return helper(null, head);
}

// Driver code
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const newHead = reverseList(head);
let curr = newHead;
let output = '';
while (curr) {
    output += curr.val + ' ';
    curr = curr.next;
}
console.log(output.trim());

Line Notes

function helper(prev, curr) {Helper function carries previous and current nodes for recursion

if (!curr) return prev;Base case: end of list reached, return previous as new head

let nextTemp = curr.next;Save next node before reversing pointer

curr.next = prev;Reverse current node's pointer to previous

return helper(curr, nextTemp);Recurse forward with updated pointers

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node visited once, recursion stack depth is n

💡 Similar to pure recursion, but parameters make pointer changes clearer; still risks stack overflow for large n.

Interview Verdict: Accepted but less preferred than iterative

Good for understanding recursion with parameters, but iterative is safer and more common in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Iterative reversal is the best approach to code in interviews due to its efficiency and safety. Recursive methods are good for understanding but risk stack overflow.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive Reversal)	O(n)	O(n) due to recursion stack	Yes (deep recursion)	N/A	Mention only - never code unless asked for recursion
2. Iterative Reversal Using Three Pointers	O(n)	O(1)	No	N/A	Code this approach in 95% of interviews
3. Recursive Reversal with Helper Function	O(n)	O(n) due to recursion stack	Yes (deep recursion)	N/A	Good to mention for understanding recursion with parameters

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force recursive approach to show understanding, followed by the optimal iterative approach. Practice coding and testing edge cases.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force recursive approach to show understanding of linked list reversal.Explain the iterative approach as the optimal solution.Write clean, bug-free code for the iterative method.Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of pointer manipulation, ability to handle edge cases, and write clean, efficient code without bugs or stack overflow.

Common Follow-ups

• How to reverse only a part of the linked list? → Use pointers to isolate and reverse sublist.
• Can you reverse the list recursively without extra parameters? → Yes, the pure recursion approach.

💡 Follow-ups test your ability to adapt the reversal logic to variations and deepen your understanding of recursion and iteration.

🔍

Pattern Recognition

When to Use

1) Problem involves reversing or reordering linked list nodes in-place, 2) Requires O(1) extra space, 3) Mentions singly linked list, 4) Needs to return new head of reversed list.

Signature Phrases

reverse the linked listin-place reversalreturn the new head

NOT This Pattern When

Reversing arrays or strings is different; also, problems requiring new list creation are not in-place linked list reversal.

Similar Problems

Reverse Linked List II - reverse a sublist within the listReverse Nodes in k-Group - reverse nodes in groups of kPalindrome Linked List - uses reversal to check palindrome

Practice

1. You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. You need to add the two numbers and return the sum as a linked list. Which approach guarantees an optimal solution with O(max(m, n)) time and O(1) extra space?

easy

A. Use a recursive approach that creates a new list for the sum, handling carry via recursion.

B. Iteratively traverse both lists simultaneously, modifying one list in-place to store the sum and carry.

C. Convert both linked lists to integers, add them, then convert the sum back to a linked list.

D. Use a brute force approach that creates a new list node for each digit sum, ignoring in-place modification.

Solution

1. Step 1: Understand the problem constraints

   The problem requires adding two numbers represented as linked lists in reverse order, aiming for optimal time and space.

2. Step 2: Identify the approach that modifies input in-place

   Iterative traversal with in-place modification reuses existing nodes, achieving O(max(m, n)) time and O(1) extra space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative approach avoids extra space and handles carry efficiently [OK]

Hint: In-place iterative approach saves space and time [OK]

Common Mistakes:

• Assuming recursion is always optimal
• Ignoring space complexity by creating new nodes
• Converting lists to integers causes overflow

2. Given two singly linked lists that may or may not intersect, which approach guarantees finding the intersection node in O(m + n) time and O(1) space without modifying the lists?

easy

A. Store all nodes of the first list in a hash set, then check each node of the second list against the set.

B. Use nested loops to compare every node in the first list with every node in the second list.

C. Use two pointers starting at each list head, switching heads when reaching the end, to equalize path lengths and find the intersection.

D. Sort both lists by node values and then scan simultaneously to find matching values.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the intersection node without extra space and in linear time.

2. Step 2: Evaluate approaches

   Nested loops (B) are O(m*n), hash set (C) uses extra space, sorting (D) is invalid as node values may not be unique and sorting modifies lists. The two-pointer approach (A) equalizes path lengths by switching heads, ensuring both pointers traverse equal total lengths and meet at the intersection or end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is O(m+n) time and O(1) space [OK]

Hint: Two pointers switching heads equalize lengths [OK]

Common Mistakes:

• Confusing node values with node references
• Using extra space unnecessarily
• Assuming sorting helps with intersection

3. You are given a sorted singly linked list and need to remove all duplicate nodes so that each element appears only once. Which approach guarantees an optimal in-place solution with linear time complexity and constant extra space?

easy

A. Use a hash set to track seen values and remove duplicates by reconstructing the list.

B. Use a nested loop to compare each node with all subsequent nodes and remove duplicates.

C. Iterate once through the list, comparing each node with its next node and removing duplicates in-place.

D. Sort the list first, then remove duplicates by scanning through it.

Solution

1. Step 1: Understand the problem constraints

   The list is already sorted, so duplicates appear consecutively, allowing a single pass to remove them efficiently.

2. Step 2: Identify the optimal approach

   Iterating once and comparing each node with its next node lets us remove duplicates in-place with O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with pointer manipulation matches optimal solution [OK]

Hint: Sorted list allows single pass duplicate removal [OK]

Common Mistakes:

• Thinking nested loops are needed despite sorted input

4. Consider the following buggy code snippet for removing the nth node from the end of a linked list. Which line contains the subtle bug that causes incorrect behavior when removing the head node?

medium

A. Line 13: Wrong condition for node removal

B. Line 10: Incorrect base case for recursion

C. Line 5: Missing dummy node initialization

D. Line 15: Returning head instead of dummy.next

Solution

1. Step 1: Identify missing dummy node

   Without a dummy node, removing the head node causes pointer errors or incorrect list head.

2. Step 2: Check recursion call and return

   Recursion is called on head, but no dummy means no safe predecessor to update head pointer.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Dummy node is essential to handle head removal safely [OK]

Hint: Always use dummy node to handle head removal [OK]

Common Mistakes:

• Not using dummy node
• Incorrect recursion base case
• Returning wrong node after removal

5. What is the time and space complexity of the recursive approach to reverse a sublist between positions left and right in a singly linked list of length n?

medium

A. Time: O(n), Space: O(1) due to in-place reversal

B. Time: O(n^2), Space: O(n) due to repeated traversals

C. Time: O(right - left), Space: O(right - left) due to partial recursion

D. Time: O(n), Space: O(n) due to recursion stack

Solution

1. Step 1: Analyze time complexity

   The recursive approach visits each node at most once, so time complexity is O(n).

2. Step 2: Analyze space complexity

   Recursion depth can be up to n in worst case, so space complexity is O(n) due to recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack space is often overlooked but critical here [OK]

Hint: Recursion adds O(n) space, not O(1) [OK]

Common Mistakes:

• Assuming constant space for in-place reversal
• Confusing partial recursion depth with full list length
• Mistaking time complexity as quadratic