Circular Linked Lists

July 2026 · 20 min read

Take the last node's next and, instead of nullptr, point it back at the first node. That one change — removing the end — turns a list into a ring, and rings are how you model anything that cycles: a scheduler handing out time slices, a fixed-size buffer, a playlist on repeat, players taking turns. The ring also comes with two traps: there is no null to stop your loop, and the “obvious” loop condition visits nothing. This post gives you the representations, the safe traversal, the O(1) splices, and the classic Josephus problem two ways.

What Makes a List Circular

A circular singly linked list replaces the terminating nullptr with a link back to the head: following next forever cycles through the elements. A circular doubly linked list additionally closes the prev chain, so the head's prev is the tail and the tail's next is the head — exactly the sentinel ring behind std::list, minus the sentinel. The defining property either way:

// Non-empty circular singly linked list:
last->next == head;      // there is no nullptr anywhere in the ring
// A one-node ring points at itself:
solo->next == solo;

That missing nullptr is the whole personality of the structure. It is what makes both ends reachable from one pointer, and it is what makes a careless traversal spin forever.

The Tail-Only Representation

Here is the key insight of this entire post, and the reason circular lists are worth knowing: keep a pointer to the tail, not the head. In a ring, tail->next is the head — so a single tail pointer gives you O(1) access to both ends, and therefore O(1) push_front and O(1) push_back, from one pointer, with no doubly linked overhead.

struct Node { int val; Node* next; explicit Node(int v) : val(v), next(nullptr) {} };

struct Ring {
    Node* tail = nullptr;                 // tail->next is the head; null when empty

    bool  empty() const { return tail == nullptr; }
    Node* head()  const { return tail ? tail->next : nullptr; }

    void push_front(int v) {              // O(1)
        Node* n = new Node(v);
        if (tail == nullptr) { n->next = n; tail = n; return; } // 1-node ring
        n->next    = tail->next;           // new node -> old head
        tail->next = n;                    // tail -> new node (the new head)
    }

    void push_back(int v) {               // O(1): same splice, then advance tail
        push_front(v);
        tail = tail->next;                 // the freshly inserted node becomes tail
    }
};

Read push_back again: inserting at the front and then moving tail onto the new node makes that node the last element — an append — in constant time. A plain singly linked list needed either an O(n) walk or a separate tail pointer to append; the ring gets it from the one pointer it already keeps.

Traversing Without Looping Forever

With no nullptr to test, the naive loop is a bug in two different ways. Write while (p != head) starting from p = head and the condition is false on entry, so the body never runs — you visit nothing. Fix that by starting one node in and you instead loop forever on a single-node ring. The correct shape is a do–while: act first, then test against a remembered start.

void print(const Ring& r) {
    if (r.empty()) return;                 // 1. empty ring: nothing to do
    const Node* start = r.head();
    const Node* p = start;
    do {
        std::cout << p->val << ' ';
        p = p->next;
    } while (p != start);                   // 2. stop once we return to start
}

The two guards matter independently. The empty check handles tail == nullptr, where head() is null and there is no start. The do–while handles every non-empty ring including the one-node case, because the body runs once before the equality test can end it. Any circular-list bug that “prints nothing” or “hangs” is one of these two guards missing.

Splitting and Joining in O(1)

Joining two rings is O(1) in the tail-only representation — four pointer writes, no traversal. Given the two tails, cross-link the tails to each other's heads:

// Concatenate ring B after ring A; both identified by their tails. Returns new tail.
Node* join(Node* tailA, Node* tailB) {
    if (tailA == nullptr) return tailB;
    if (tailB == nullptr) return tailA;
    Node* headA = tailA->next;
    Node* headB = tailB->next;
    tailA->next = headB;     // A's tail -> B's head
    tailB->next = headA;     // B's tail -> A's head, re-closing the ring
    return tailB;            // B's tail is now the overall tail
}

Splitting a ring into two halves uses the fast/slow walk you will meet properly in Fast & Slow Pointers: advance one cursor by one and another by two until the fast one laps back to the head, at which point the slow one sits at the midpoint. Then close each half into its own ring.

void split(Node* head, Node** first, Node** second) {
    if (head == nullptr) { *first = *second = nullptr; return; }
    Node* slow = head;
    Node* fast = head;
    while (fast->next != head && fast->next->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast->next->next == head) fast = fast->next;  // even length: land fast on last
    *first  = head;
    *second = slow->next;
    fast->next  = *second;      // close the second ring
    slow->next  = *first;       // close the first ring
}

Converting Linear ↔ Circular

The conversions are the natural inverses, and both are cheap once you accept an O(n) walk to find the end going one way:

Node* to_circular(Node* head) {           // returns the tail
    if (head == nullptr) return nullptr;
    Node* p = head;
    while (p->next != nullptr) p = p->next; // O(n): find the last node
    p->next = head;                         // close the ring
    return p;
}

Node* to_linear(Node* tail) {             // returns the head
    if (tail == nullptr) return nullptr;
    Node* head = tail->next;
    tail->next = nullptr;                   // O(1): cut the ring open
    return head;
}

Going circular→linear is O(1) because the tail already knows the head; going linear→circular costs one walk to locate the tail, after which you would keep the tail pointer and never pay that walk again.

Where Circular Lists Show Up

• Round-robin scheduling. An OS keeps runnable processes in a ring and hands each a time slice in turn; after the last it wraps to the first. The scheduler holds one current pointer and advances it — no bounds logic, ever.
• Ring / circular buffers. A fixed-capacity producer/consumer queue where the write and read cursors chase each other around. (Usually array-backed for cache locality, but the topology is a ring.)
• Music playlist on repeat. “Repeat all” is literally a circular list: the last track's next is the first.
• Multiplayer turn order. Players sit in a ring; play passes to current->next, and eliminating a player is a single unlink. Which is exactly the next problem.

The Josephus Problem

n people stand in a circle. Starting from person 1, you count k and eliminate the k-th person, then resume counting from the next survivor, repeating until one person remains. Who survives? A circular list simulates the story directly — keep a cursor and a trailing pointer, count k−1 hops, unlink the k-th:

int josephus_sim(int n, int k) {
    if (n <= 0) return -1;
    Node* tail = nullptr;                       // build ring of values 1..n
    for (int i = 1; i <= n; ++i) {
        Node* nd = new Node(i);
        if (tail == nullptr) { nd->next = nd; tail = nd; }
        else { nd->next = tail->next; tail->next = nd; tail = nd; }
    }
    Node* cur = tail->next;                      // start at person 1 (the head)
    Node* prev = tail;
    while (cur->next != cur) {                    // until a single node remains
        for (int step = 1; step < k; ++step) {   // count k-1 hops
            prev = cur;
            cur  = cur->next;
        }
        prev->next = cur->next;                   // eliminate the k-th
        delete cur;
        cur = prev->next;                         // resume from the next survivor
    }
    int survivor = cur->val;
    delete cur;
    return survivor;                             // 1-indexed
}

Each of the n−1 eliminations walks up to k−1 nodes, so the simulation is O(nk) time and O(n) space. Correct, intuitive, and exactly what the animation below shows.

Watch the Elimination

Seven people in a circle, k = 3. Each step counts three around the ring and eliminates that person; watch the ring shrink until one survivor is left. The order of elimination is 3, 6, 2, 7, 5, 1 — survivor 4.

From O(nk) Simulation to the O(n) Recurrence

The simulation is wasteful because it re-walks the ring. There is a beautiful closed recurrence instead. Let J(n, k) be the 0-indexed position of the survivor among n people. One person survives trivially at position 0, and eliminating the first victim renumbers the remaining circle:

J(1, k) = 0
J(n, k) = (J(n-1, k) + k) % n

The mapping is the whole trick. After the first person (at 0-indexed position k-1) is eliminated, n−1 people remain, and counting restarts from the next person. If you renumber that smaller circle starting at 0 from the restart point, the survivor sits at J(n-1, k). To translate that back into the original numbering you shift forward by k and wrap: (J(n-1, k) + k) % n. Iterate from 1 up to n and you get an O(n) time, O(1) space solution:

int josephus(int n, int k) {
    int r = 0;                              // J(1, k) = 0
    for (int m = 2; m <= n; ++m)            // grow the circle to n
        r = (r + k) % m;
    return r + 1;                           // +1 to make it 1-indexed
}

Here is the recurrence unrolled for n = 7, k = 3. The final r = 3 (0-indexed) is person 4 (1-indexed) — the same answer the simulation and the animation produce:

Check Yourself

Each item is a situation; pick the statement that is actually correct for a circular list.

Practice

• LeetCode 622 — Design Circular Queue ring the ring buffer as an explicit exercise.
• LeetCode 641 — Design Circular Deque both-ends O(1) push/pop at both ends of a ring.
• LeetCode 708 — Insert into a Sorted Circular Linked List wrap the min/max wraparound is the whole difficulty.
• LeetCode 1823 — Find the Winner of the Circular Game josephus literally the Josephus recurrence.
• LeetCode 142 — Linked List Cycle II detect a partial ring; find where the cycle begins.
• LeetCode 725 — Split Linked List in Parts split the splitting logic, on a linear list.