114. Why can circular linked lists be concatenated in O(1), and what are other uses of circular lists?
MediumLinked lists
Technical
Show model answer
If you keep a pointer to the tail of each circular list instead of the head, the head is just `tail.next`. To concatenate A and B: save `headA = tailA.next`, set `tailA.next = tailB.next` (B's head), set `tailB.next = headA`, and the result's tail is tailB. No traversal is needed, so it is O(1), whereas a plain singly linked list with only a head pointer needs O(n) to find its tail.
Circular lists also model round-robin scheduling, the Josephus problem, buffers that wrap around, and repeating playlists. Watch out for infinite loops: traversal must stop when it returns to the starting node rather than when it sees null.