Construction

What is this?

Some problems are hard because the algorithm is hard. These two are hard because the algorithm is obvious and the boundaries are not. Inserting into a sorted circular list is a three-line splice — except at the one place in the ring where the values stop ascending, and except when every value is identical, and except when the list is empty. Miss any of those and you have an infinite loop rather than a wrong answer.

The second problem is a different kind of trap: you are asked to weight items by how shallow they are, but you do not learn the maximum depth until you have already walked the whole structure.

💡 Fun fact: Nested List Weight Sum II has a solution that looks like sleight of hand. Instead of finding the maximum depth and then weighting, you keep a running total of every level's unweighted sum and add that running total to the answer once per level. A value at depth 1 in a 3-deep structure ends up counted three times, one at depth 3 exactly once — which is precisely the inverse-depth weight. You never compute a depth at all; repetition does the multiplication for you.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: enumerate the boundary cases before writing the loop. A sorted ring has exactly one discontinuity and two degenerate shapes; a depth-weighted sum has one unknown you can either resolve with a first pass or dissolve by accumulating differently.

1. The three insertion cases

Walk prev/curr around the ring once. Insert when any of these holds:

The wrap case is the one that gets missed. In a ring like 3 → 4 → 1 → 2 → (3), the descent from 4 to 1 is the seam — and inserting 5 (a new max) or 0 (a new min) both happen there, which is why one test covers two situations that feel opposite.

The uniform case is why the loop must be bounded. 1 → 1 → 1 never satisfies either test, so without a "stop after one full lap" guard the walk never terminates.

2. The inverse-depth accumulation

Two approaches, and the contrast is the lesson.

Two passes. Find maxDepth, then walk again summing value × (maxDepth − depth + 1). Direct, obvious, easy to defend.

One pass, no depths. Process level by level. Keep levelSum (the running total of every value seen so far, unweighted) and add it to answer after each level:

[[1,1],2,[1,1]]        level 1 holds: 2          level 2 holds: 1,1,1,1

level 1:  levelSum = 2            answer = 2
level 2:  levelSum = 2 + 4 = 6    answer = 2 + 6 = 8

check: depth-1 value 2 has weight 2 → 4;  four depth-2 ones have weight 1 → 4
                                                             total = 8 ✓

The value 2 was folded into levelSum at level 1 and then re-added at level 2, so it contributed twice — exactly its weight. Shallow things get counted more often because they were added earlier.

3. Where you'll actually meet this

• Scheduler run-queues. Circular sorted lists of tasks by priority or deadline, spliced into on arrival — the wrap point is a real source of production bugs.
• Ring buffers with ordering. Any structure that keeps sorted order while wrapping faces the same seam problem.
• Consistent hashing. Placing a new node on a hash ring is precisely "insert into a sorted circular list", and the wrap-around at the top of the keyspace is the case that must be handled.
• Document and configuration trees. Weighting nested content by how shallow it sits — outlines, permission inheritance, nested JSON scoring — is the second problem's shape.
• Organisational rollups. Summing values up a hierarchy where higher levels count for more is inverse-depth weighting under a different name.

4. Problems in this chapter

▶ Insert into a Sorted Circular Linked List

Splice a value into a ring while preserving sorted order. Three cases, one full-lap termination guard, and an empty-list case that must point the new node at itself.
Pattern: ring traversal with case analysis. Target: O(n) time, O(1) space.

▶ Nested List Weight Sum II

Sum integers weighted by inverse depth. Either find the maximum depth first, or accumulate level sums and add the running total once per level so shallow values are counted more often.
Pattern: level-order accumulation. Target: O(n) time, O(n) space for the level queue.

5. Common pitfalls 🚫

• No termination guard on the ring walk. With all-equal values neither insertion test ever fires; stop after returning to the entry node.
• Forgetting the empty list. A brand-new single node must point to itself, or the ring invariant is broken for every later insertion.
• Treating new-max and new-min as separate cases. Both belong at the seam; one combined test is simpler and less error-prone.
• Comparing with strict <. Duplicates are legal in a sorted ring, so the in-order test needs <= on at least one side.
• Confusing the two weight-sum variants. In the first version weight increases with depth (a plain recursion works); here it decreases, which is why the naive recursion cannot know the weight when it reaches a leaf.
• Recomputing depth per element. If you go the two-pass route, compute maxDepth once, not per value.

6. Key takeaways

1. Enumerate the boundaries before the loop. In a ring that means the seam, the uniform list, and the empty list.
2. The wrap point is where new extremes belong — one test, two situations.
3. Bound every circular traversal. One full lap, then stop.
4. When a weight depends on something you learn later, either take a first pass to learn it or restructure the accumulation so it never needs to be known.
5. Repetition can stand in for multiplication. Adding a running sum once per level is inverse-depth weighting.
6. Why interviewers like it: both problems are short, and both fail on inputs a hurried candidate never considers — which makes them efficient tests of care rather than cleverness.

Order: Insert into a Sorted Circular Linked List → Nested List Weight Sum II.