What is the time complexity of reversing a singly linked list?

The time complexity is O(n), where n is the number of nodes in the list.

How Do You Reverse a Linked List? | FullStackPrep.Dev

Q: How do you reverse a linked list?

To reverse a linked list, iterate through the list and reverse the direction of the next pointers using three pointers: prev, current, and next.

💡 Concept Name

Reversing a Linked List – The method of reversing the direction of pointers in a singly linked list, making the last node the new head and traversing the list backwards.

📘 Quick Intro

Reversing a singly linked list is a classic interview problem that involves manipulating pointers to reverse the order of nodes, ensuring the traversal order is flipped.

🧠 Analogy / Short Story

Picture a line of people where each points to the next. To reverse the line, you make each person point to the one behind them, so the last person leads the new line and the order reverses.

🔧 Technical Explanation

🔁 Utilize three pointers: prev, current, and next to safely reverse links.
⬅ Redirect current.Next to prev each iteration.
➡ Advance prev and current forward by one node.
🏁 After completion, prev points to the new head of the reversed list.
🕒 Time complexity: O(n) — iterates once through the list; Space complexity: O(1).

🎯 Purpose & Use Case

✅ Enables stack-like behavior in linked lists.
✅ Useful for undo/redo operations and backtracking.
✅ Facilitates traversal or output in reverse order.

💻 Real Code Example

public class Node
{
    public int Data;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

public class LinkedList
{
    public Node Head;

    public void Reverse()
    {
        Node prev = null;
        Node current = Head;
        Node next = null;

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

        Head = prev;
    }

    public void Print()
    {
        Node temp = Head;
        while (temp != null)
        {
            Console.Write(temp.Data + " ");
            temp = temp.Next;
        }
    }
}

// Usage
LinkedList list = new LinkedList();
list.Head = new Node(1);
list.Head.Next = new Node(2);
list.Head.Next.Next = new Node(3);
list.Reverse();
list.Print(); // Output: 3 2 1

❓ Interview Q&A

Q1: What does it mean to reverse a linked list?
A: Changing the direction of all the pointers so that the last node becomes the head and the head becomes the last node.

Q2: Can you reverse a singly linked list iteratively?
A: Yes, by changing the next pointers of each node using a loop.

Q3: Can you reverse a singly linked list recursively?
A: Yes, by recursively reversing the rest of the list and adjusting pointers.

Q4: What pointers are needed to reverse a linked list iteratively?
A: Previous, current, and next pointers.

Q5: What is the time complexity of reversing a linked list?
A: O(n), where n is the number of nodes.

Q6: What is the space complexity of iterative reversal?
A: O(1), as it uses constant extra space.

Q7: What is the space complexity of recursive reversal?
A: O(n), due to the recursion call stack.

Q8: Is it possible to reverse a doubly linked list?
A: Yes, by swapping the previous and next pointers for all nodes.

Q9: What are common use cases for reversing linked lists?
A: Undo operations, palindrome checking, and algorithmic problems.

Q10: Can reversing a linked list break the list?
A: Yes, if pointers are not handled carefully during reversal.

📝 MCQs

Q1. What is the main operation in reversing a linked list?

Swapping data
Reversing pointers
Deleting nodes
Adding nodes

Q2. Which pointers are used in iterative reversal?

Head, tail
Previous, current, next
Next only
None

Q3. What is time complexity of linked list reversal?

O(1)
O(n)
O(log n)
O(n^2)

Q4. What is space complexity of iterative reversal?

O(1)
O(n)
O(log n)
O(n^2)

Q5. What is space complexity of recursive reversal?

O(1)
O(n)
O(log n)
O(n^2)

Q6. Can doubly linked lists be reversed?

No
Yes
Only singly linked
Depends

Q7. What happens if pointers are mishandled?

Nothing
List breaks
Faster reversal
Memory leak

Q8. Is recursive reversal efficient in space?

Yes
No
Depends
Sometimes

Q9. What is a common use of reversed linked lists?

Sorting
Palindrome checking
Searching
Hashing

Q10. Can linked list data be swapped instead of pointers?

No
Yes, but inefficient
Always preferred
Not possible

💡 Bonus Insight

Recursive reversal is elegant but beware of stack overflow on large lists. Reversing doubly linked lists involves swapping prev and next pointers for each node.

📄 PDF Download

Need a handy summary for your notes? Download this topic as a PDF!

📄 PDF Download Coming Soon

How Do You Reverse a Linked List?