Data Structures u0026 Algorithms: Advanced Linked List Concepts Quiz

Challenge your understanding of singly, doubly, and circular linked lists as well as advanced techniques like Floyd’s Cycle Detection and merging operations. This quiz is designed to test your knowledge of key data structures and complex algorithmic strategies.

1. Singly Linked List: Node Deletion

   In a singly linked list, what is the minimum information required to delete a node ‘X’ that is not the last node, given only a pointer to ‘X’?

   1. Store the head pointer and traverse from the start
   2. Access previous node and set its next to NULL
   3. Swap X with head and delete head
   4. Copy data from the next node into X and delete the next node
   5. Set X to NULL without modifying other nodes

2. Doubly Linked List: Reverse Traversal

   When performing reverse traversal of a doubly linked list, what must be accessed from each node to move to the previous element?

   1. random pointer
   2. main pointer
   3. head pointer
   4. prev pointer
   5. next pointer

3. Circular Linked List: Infinite Loops

   Which condition will guarantee an infinite loop in a singly circular linked list traversal?

   1. while(current != head)
   2. while(current != tail)
   3. while(current.next != head)
   4. while(current.next != current)
   5. while(current != NULL)

4. Floyd’s Cycle Detection: Tortoise and Hare

   How does Floyd’s Cycle Detection algorithm ensure that a cycle exists in a linked list when both pointers meet at a node?

   1. Both pointers reach NULL at the same time
   2. Both slow and fast pointers revisit a node simultaneously
   3. Fast pointer jumps to head after every step
   4. Only slow pointer ever repeats a node
   5. Both pointers skip the cycle and exit

5. Merging Two Sorted Linked Lists

   Given two sorted singly linked lists, what is the most efficient approach to merge them into a single sorted list using O(1) auxiliary space?

   1. Reverse both lists before merging
   2. Copy both lists to arrays and merge arrays
   3. Insert all nodes into a hash set
   4. Iteratively compare heads and link the smaller
   5. Recursively copy each node to a new list

6. Time Complexity: Doubly Linked List Deletion

   What is the time complexity for deleting a given node in a doubly linked list, provided a direct reference to that node, but no head or tail pointers?

   1. O(log n)
   2. O(n log n)
   3. O(n)
   4. O(1)
   5. O(2n)

7. Circular Linked List: Insertion After Tail

   When inserting a node after the tail in a circular singly linked list containing ‘n’ nodes, which pointers must be updated for proper linkage?

   1. No pointers, structure updates automatically
   2. New node’s prev only
   3. Only the new node’s next
   4. Tail’s next and the new node’s next
   5. Head’s next and tail’s next

8. Detecting Loop Starting Point

   After identifying a cycle using Floyd’s algorithm, how can the start node of the cycle in a linked list be found?

   1. Rearrange nodes in reverse
   2. Move one pointer to head and advance both one step until meeting
   3. Remove random nodes until the loop breaks
   4. Check for NULL pointers
   5. Count nodes in the cycle and jump that many from head

9. Edge Case: Merging with Empty Lists

   If you merge a non-empty sorted linked list L1 with an empty sorted linked list L2, what should be the resulting merged list?

   1. L1 remains unchanged
   2. Both lists are deleted
   3. L2 becomes a copy of L1
   4. Merged list cycles back to head
   5. L1 and L2 are concatenated twice

10. Tail Pointer Utility in Linked Lists

    Which of the following operations is optimized by maintaining a direct tail pointer in a singly linked list?

    1. Faster deletion of middle nodes
    2. Efficient reverse traversal
    3. Quick access to minimum element
    4. Constant-time insertion at the end
    5. Loop detection using tail reference