Data Structures Linked Lists 2

Question 1

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

Accepted Answer

O(n)

Answer

Reversing requires visiting each node exactly once to redirect its next pointer, resulting in O(n) time complexity.

Question 2

How can two sorted linked lists be merged in O(m+n) time?

Accepted Answer

Compare heads iteratively and link the smaller node

Answer

By comparing the heads of both lists and always linking the smaller node, you merge them in O(m+n) time with O(1) extra space.

Question 3

What is a sentinel (dummy) head node used for in linked list implementations?

Accepted Answer

To simplify edge cases by eliminating null checks at the head

Answer

A dummy head node ensures the list is never truly empty from the algorithm's perspective, eliminating special-case code for head insertions and deletions.

Question 4

Which data structure can be implemented using two linked lists to support O(1) push, pop, and min operations?

Accepted Answer

Min-stack

Answer

A min-stack uses a second stack to track the current minimum, enabling O(1) retrieval of the minimum alongside standard stack operations.

Question 5

What is the space complexity of a recursive linked list reversal?

Accepted Answer

O(n)

Answer

Recursive reversal uses O(n) call stack space because each node generates a recursive call frame before the base case is reached.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Linked Lists 2