Linked Lists MCQ Practice Test

Q1. Consider a doubly linked list where each node contains an integer and pointers to the previous and next nodes. A function 'swapPairs' is designed to swap consecutive pairs of nodes. For example, if the list is 1 -> 2 -> 3 -> 4, after calling 'swapPairs', it should become 2 -> 1 -> 4 -> 3. However, there's a bug in the implementation. Given the following code snippet (assuming necessary node structure and functions exist): c++ void swapPairs(Node*& head) { if (!head || !head->next) return; Node* current = head; head = head->next; // Update head while (current && current->next) { Node* nextPair = current->next->next; current->next->next = current; current->next = nextPair; current = nextPair; } } What is the incorrect behavior or edge case this code snippet will fail to handle correctly?

• A. The function correctly swaps all pairs of nodes.
• B. It fails to handle lists with an odd number of nodes.
• C. It only swaps the first pair of nodes and leaves the rest unchanged.
• D. It introduces memory leaks by losing pointers to some nodes. ✓

Q2. You have a singly linked list where each node contains an integer and a pointer to the next node. The list is initially empty. You perform the following operations sequentially: insert 5 at the head, insert 10 at the tail, insert 2 at the head. What is the value of the node immediately following the head node after these operations?

• A. 10
• B. 5 ✓
• C. 2
• D. There is no node following the head node

Q3. You have a singly linked list where each node contains an integer and a pointer to the next node. You want to insert a new node with the value 77 between the nodes containing 55 and 99. Assuming you have pointers 'before' pointing to the node with 55 and 'after' pointing to the node with 99, what line of code correctly inserts the new node?

• A. newNode.next = before.next; before.next = newNode; ✓
• B. newNode.next = after.next; after.next = newNode;
• C. newNode = before.next; before.next = 77;
• D. after.next = newNode; newNode.next = before;

Q4. Given a doubly linked list with a sentinel node, what is the time complexity of finding the middle node using the slow and fast pointer approach?

• A. O(1)
• B. O(n) ✓
• C. O(log n)
• D. O(n^2)

Q5. Given a doubly linked list with a custom implementation of a “skip” operation that moves the cursor to the next node that has a value greater than the current node’s value, what is the time complexity of this operation?

• A. O(1)
• B. O(n) ✓
• C. O(n^2)
• D. O(log n)

Q6. Consider a linked list with the following structure: 1 -> 2 -> 3 -> 4 -> 5. What is the time complexity of finding the node with value 3 using a recursive function that traverses the list by following the next pointer of each node?

• A. O(1)
• B. O(n) ✓
• C. O(n/2)
• D. O(log n)

Q7. Given a doubly-linked list with a sentinel node, what is the time complexity of the operation to rotate the list by $k$ nodes, where $k$ is the number of nodes to rotate, and the rotation is performed in-place?

• A. O(1)
• B. O(n) ✓
• C. O(n + k)
• D. O(n · k)

Q8. Given a doubly linked list with a sentinel node, what is the time complexity of deleting a node at a given position k, where k is the index of the node to be deleted?

• A. ±π(k) time complexity, where n is the number of nodes in the list
• B. O(1) time complexity, because the sentinel node provides a constant-time access to the head of the list
• C. O(n) time complexity, because we need to traverse the list from the head to find the node at position k ✓
• D. O(1) time complexity, because the node at position k is known in advance

Q9. In a doubly linked list, given a node, how do you delete the node itself without changing the next and previous pointers of adjacent nodes?

• A. Delete the node by updating the next pointer of the previous node to skip the current node, and then update the previous pointer of the next node to skip the current node. ✓
• B. Delete the node by setting the next pointer of the previous node to the next node of the current node, and then set the previous pointer of the next node to the previous node of the current node.
• C. Delete the node by updating the next pointer of the previous node to the next node of the current node, and then recursively delete the next node.
• D. Delete the node by setting the next pointer of the previous node to the current node's previous node, and then set the previous pointer of the current node's next node to the current node's previous node.

Q10. Given a doubly linked list with a sentinel node at the head, what is the time complexity of inserting a new node at a specific position in the list, where the position is given as a distance from the end of the list?

• A. O(1)
• B. O(n) ✓
• C. O(n^2)
• D. O(2^n)

That was just a sample. Sign up to unlock the full question bank with timed tests and certificates.