Skip to interview prep
Apexed

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.

Why can circular linked lists be concatenated in O(1), and what are other uses of circular lists — Data structures & algorithms interview question — Apexed