Data Structures Linked Lists 2 ā Questions and Answers
Question 1: What is the time complexity of reversing a singly linked list iteratively?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(nĀ²)
Correct answer: O(n)
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?
- Concatenate then sort
- Use a priority queue
- Compare heads iteratively and link the smaller node (Correct answer)
- Copy to arrays, merge, rebuild
Correct answer: Compare heads iteratively and link the smaller node
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?
- To store the list's length
- To simplify edge cases by eliminating null checks at the head (Correct answer)
- To speed up search operations
- To enable random access
Correct answer: To simplify edge cases by eliminating null checks at the head
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?
- Priority queue
- Min-stack (Correct answer)
- Circular buffer
- Deque
Correct answer: Min-stack
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?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(nĀ²)
Correct answer: O(n)
Recursive reversal uses O(n) call stack space because each node generates a recursive call frame before the base case is reached.
Question 6: How do you detect the start of a cycle in a linked list after detecting its existence?
- Move fast pointer to head, advance both one step at a time until they meet (Correct answer)
- Count nodes in the cycle and skip that many from head
- Use a hash map to record first-seen positions
- Reverse the list and find the first repeated node
Correct answer: Move fast pointer to head, advance both one step at a time until they meet
After Floyd's detection finds a meeting point, resetting one pointer to the head and advancing both one step at a time causes them to meet exactly at the cycle's entrance.
Data Structures Linked Lists 2
What is the time complexity of reversing a singly linked list iteratively?