How would you delete the head node of a singly linked list, and what is the time complexity?

• A. head = head.next; deallocate old head; O(1)
• B. last.next = head; head = head.next; O(n)
• C. head.next = head.next.next; O(1)
• D. Delete the tail node; O(n)

Answer: (A)

Deleting the head node is a simple pointer update and deallocation. You re-point the head to the next node (head = head.next) and then free the old head. This is done in constant time, O(1), because it doesn’t depend on the length of the list.

Edge cases worth noting: if the list is empty, nothing happens. If there is only one node, head.next is null, so after the operation head becomes null and the single node is freed.

Other approaches would either modify the wrong part of the list or require traversing to the tail, which would take linear time. For example, touching the tail or trying to bypass a node without updating the head wouldn’t actually remove the head correctly, and needing to walk through the list to reach the end would be O(n).