Data Structures Linked Lists 2

Question 1

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

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n²)

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

Concatenate then sort

Answer

Use a priority queue

Answer

Copy to arrays, merge, rebuild

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

To store the list's length

Answer

To speed up search operations

Answer

To enable random access

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

Priority queue

Answer

Circular buffer

Answer

Deque

Question 5

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

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n²)

Question 6

How do you detect the start of a cycle in a linked list after detecting its existence?

Accepted Answer

Move fast pointer to head, advance both one step at a time until they meet

Answer

Count nodes in the cycle and skip that many from head

Answer

Use a hash map to record first-seen positions

Answer

Reverse the list and find the first repeated node