Exercises — Circular linked list — applications

WHAT we look at: the next pointer of the last node.

• Top chain: last node's next = null (the ground symbol ⏚). That is a plain Singly Linked List.
• Bottom chain (red): last node's next = the head (the curved loop back to node 1). That closed loop is the circular linked list.

The one distinguishing value: lastNode.next. If it is null → normal list. If it equals head → circular. Nothing else about the nodes differs.

True. Because the loop is closed, following next from any node eventually visits all nodes and returns to your start. The head is not privileged — it is just the node someone chose to call "first." (Contrast: in a singly linked list, starting from the middle you can never reach the nodes behind you.)

All three loop for the same structural reason: after the last item comes the first again.

• (a) Round-Robin Scheduling: after the last process's time slice, control returns to the first process.
• (b) Playlist repeat: after the last song, play song 1.
• (c) Josephus Problem: counting people wraps around the circle.

Track remaining burst; each turn run $\min (q,\text{remaining})$. The "runs" column = the CPU-time units actually executed that turn (from the legend: $\min (q,\text{remaining})$).

Completion order: P2, P1, P3.

How the splice stays $O(1)$ (the predecessor question). To remove a finished node we need a pointer to the node just before it. In round-robin we get that for free: we advance with a single current pointer, current = current.next. When we are about to run a process, the process we ran on the previous turn is exactly its predecessor in the circle. So we keep one extra pointer prev that always trails one node behind current (prev is set to current right before we step current = current.next). When the current process finishes, we splice it with prev.next = current.next — an $O(1)$ operation, no scan. This is why, at turn 2, removing P2 (whose predecessor P1 we still hold as prev) shrinks the circle to P1→P3→P1 with no special "wrap" code.

Count $k=3$ each round; the 3rd counted dies; counting resumes from the next living person.

• Count 1,2,3 → kill 3. Alive: 1 2 4 5 6 7.
• From 4: 4,5,6 → kill 6. Alive: 1 2 4 5 7.
• From 7: 7,1,2 → kill 2. Alive: 1 4 5 7.
• From 4: 4,5,7 → kill 7. Alive: 1 4 5.
• From 1: 1,4,5 → kill 5. Alive: 1 4.
• From 1: 1,4,1 → kill 1. Alive: 4.
• Survivor = 4.

Set up the semantics first (this is what the problem hinges on). A ring buffer has 4 physical slots, index 0..3, joined in a circle so "next after slot 3 = slot 0." We keep two pointers:

• w = write index: where the next written value goes. After a write, w = (w+1) \bmod 4.
• r = read index: the slot of the oldest unread value. After a read, r = (r+1) \bmod 4.
• A count of unread items tells us if the buffer is full (count == 4).

Overwrite rule: if you write when count == 4 (full), the new value lands on slot w — which is exactly the oldest unread slot — and we push r forward too (r = (r+1) \bmod 4), because the oldest unread datum was just destroyed. If not full, a write only advances w and increments count; a read advances r and decrements count.

Trace (start w=0, r=0, count=0, slots shown as physical array):

Final buffer (physical slots 0..3): [e, f, c, d]; read returned b. The circle is what makes "next after last = first," so the write pointer naturally lands on the oldest slot and overwrites it.

Set p = start at the top. In a plain pre-test loop while (p != start) { visit; p = p.next; }, the condition p != start is false immediately (since p == start), so the body runs zero times — you visit nothing. The do { visit; p = p.next; } while (p != start); form runs the body once before testing, so the head is visited, then we walk until we come back. This is the direct consequence of "no null": the only landmark is the start node itself, so it must be both the entry and the exit test.

Key insight: circularity forces tail.next == head, so one pointer gives $O(1)$ at both ends. A non-circular Singly Linked List with only a head needs $O(n)$ to reach the back.

If the loop is broken, the last node now points to null (a plain list). Traversal using while (p != start) will step p to null, then dereference p.next → null-pointer crash (or an infinite non-return, depending on where the break is). The p == start test never becomes true because you never come back — so the bug shows as a crash/hang, which is why the fix "after any tail change, ensure tail.next = head" (from the parent's mistakes list) is mandatory.

Empty cases first (skipping these loses nodes or makes self-loops):

• If tA == null (A empty): result is just B, return tB.
• If tB == null (B empty): result is just A, return tA.

General case (both non-empty, works even when either has a single node, since a single node satisfies t.next == t). Let hA = tA.next (head of A), hB = tB.next (head of B):

temp    = tA.next     // = hA, save A's head
tA.next = tB.next     // A's tail now points to B's head (hB)
tB.next = temp        // B's tail now points to A's head (hA)
// new tail of combined list = tB

Four assignments, $O(1)$, independent of list sizes. If A is a single node, tA == hA, and the code still correctly makes it point to B's head; likewise a single-node B. The closed loops let us "cut and re-stitch" the two circles into one without walking either — exactly why circular sibling lists make heap merge cheap.

Build up, $k=3$:

• $J(1)=0$
• $J(2)=(0+3)\mathrm{mod}2=1$
• $J(3)=(1+3)\mathrm{mod}3=1$
• $J(4)=(1+3)\mathrm{mod}4=0$
• $J(5)=(0+3)\mathrm{mod}5=3$
• $J(6)=(3+3)\mathrm{mod}6=0$
• $J(7)=(0+3)\mathrm{mod}7=3$

0-indexed survivor $=3$ → 1-indexed survivor $=3+1=4$, matching Exercise 2.2. ✓

tail.next is the front (head) of the queue; tail is the back. We treat tail == null as the empty queue.

enqueue(x) (add at back):

• Empty case (tail == null): x.next = x; tail = x; — the first node must point to itself to form the loop. → $O(1)$.
• General case: x.next = tail.next; tail.next = x; tail = x; → $O(1)$.

dequeue() (remove front):

• Empty case (tail == null): error / return "empty."
• Single-node case (tail.next == tail): the queue has one element; return it and set tail = null (now empty). → $O(1)$.
• General case: front = tail.next; tail.next = front.next; return front. → $O(1)$.

Both ends are reachable from the one tail pointer, so FIFO order costs $O(1)$ — the circular link is the head reference. The single-node and empty branches are exactly the pitfalls flagged in the parent note's mistakes.

Algorithm (slow/fast pointers, then two cuts). Start slow = head, fast = head.

Precise termination — walk fast two steps and slow one step per iteration, stopping so that slow ends on the last node of the first half:

while (fast.next != head && fast.next.next != head):
    slow = slow.next
    fast = fast.next.next

• Odd $n$ (e.g. 5): fast lands exactly on the last node (fast.next == head), the loop stops via the first sub-condition. slow has taken $\lfloor n/2\rfloor$ steps and sits on node $\lceil n/2\rceil$ — the last node of the bigger (ceil) half.
• Even $n$ (e.g. 6): fast.next.next == head triggers the stop; slow sits on node $n/2$, the last node of the first half. Both halves are $n/2$.

WHY this works: fast moves twice as fast as slow. By the time fast has travelled the whole circle once (back toward head), slow has travelled exactly half the circle — that is the essence of the two-speed trick, and it is why slow marks the midpoint without counting $n$ first.

The two cuts (let head2 = slow.next be the start of the second half):

• Close first list: slow.next = head (first half loops on itself).
• Close second list: walk from head2 to its last node (or reuse fast) and set that node's next = head2.

Complexity: one half-circle walk → $O(n)$ time, $O(1)$ extra space.

Verify $n=5$ (nodes 1..5, head=1):

• slow takes $\lfloor 5/2\rfloor =2$ steps → sits on node 3.
• First list = {1,2,3}, closed 3→1 (size $\lceil 5/2\rceil =3$).
• Second list = {4,5}, closed 5→4 (size $\lfloor 5/2\rfloor =2$).
• Sizes 3 and 2, sum $=5$. ✓

Counting argument. Fix one process $X$. Between $X$'s current turn and its next turn, the current pointer walks once around the circle: current = current.next steps through every other node exactly once before it returns to $X$. Why exactly once? Because a CLL visits each node once per full loop — the loop closes only when the pointer comes back to where it started ($X$), so no other node can be reached twice, and none can be skipped, in a single cycle.

There are $m-1$ other processes, and each, on its single visit, runs for at most one quantum $q$ (it either uses a full $q$ or finishes early and is removed — both are $\le q$). Summing these $m-1$ contributions: $W_{\max }=(m-1)q.$ (Note $X$ does not wait for its own quantum, so it is $m-1$, not $m$.) For $m=4,q=3$: $W_{\max }=(4-1)\cdot 3=9$ time units.

Could you, for every exercise above, name the single CLL property it exploits? ::: Yes — all reduce to "last.next == head, so you loop back and reach both ends / wrap counting in $O(1)$."