15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A circular linked list is a list whose last node points back to the first, so no next reference is null. To traverse it, record start = head, visit the current node, advance one link, and stop when curr returns to start. It visits each of the n nodes once, in O(n) time and O(1) auxiliary space.
| Last node | Its next points to the first node, never null |
|---|---|
| Empty list | head = null |
| One-node list | Not empty: the node's next points to itself |
| Traversal stop rule | Visit, advance, stop when curr == start |
| Traversal time and space | O(n) time, O(1) auxiliary space |
You should already be comfortable with a node that has:
valuenext referencehead reference that identifies the first nodeIn an ordinary singly linked list, the final node points to null.
In a circular singly linked list, the final node points back to the first node. A nonempty circular list therefore has no null next reference.
An empty circular list can still use:
1head = nullA one-node circular list is not empty. Its single node points to itself:
1head -> [5]
2 ^ |
3 |_|Assume every nonempty input is a finite, valid circular singly linked list. A nonempty structure containing a node whose next is null is malformed for this representation.
Reference material for the linked-node model and traversal reasoning:
Write this circular list:
1head
2 |
3 v
4[4] -> [7] -> [9]
5 ^ |
6 |_______________|The links are:
1head -> [4] -> [7] -> [9]
2 ^ |
3 |_________________|The last link is:
1[9].next = headThere is no null terminator.
Our goal is to traverse this list once and produce:
1[4, 7, 9]A null-based traversal does not work here:
1while curr != nullStarting at [4], curr moves to [7], then [9], then back to [4]. It never becomes null.
Record where traversal begins. Stop when the current node returns to that recorded start node, but only after at least one node has been visited.
Use two references:
start: the node where this traversal begancurr: the node that will be visited nextTraverse a circular list with start and curr: process curr, advance, then stop when curr is back at start. Here that visits 4, 7 and 9 once, giving output [4, 7, 9].
At first, both refer to [4].
| State | start | curr | Action | Output |
|---|---|---|---|---|
| 0 | [4] | [4], not yet visited | head and start refer to [4]; [9].next refers to [4], not null | [] |
| 1 | [4] | [4] | Process 4, then advance curr to [7] | [4] |
| 2 | [4] | [7] | Process 7, then advance curr to [9] | [4, 7] |
| 3 | [4] | [9] | Process 9, then advance curr to [4] | [4, 7, 9] |
| 4 | [4] | [4] | curr has returned to start after visits have occurred, so stop | [4, 7, 9] |
The order within each visit is:
curr.curr = curr.next.curr has returned to start.That order matters for a one-node circle.
For this one-node input:
1head -> [5]
2 ^ |
3 |_|Visit [5] first. After advancing, curr returns to start, which marks one complete cycle.
After traversal begins, keep this statement in mind:
outputcontains the nodes already visited in forward order fromstartup to, but not including,curr.curris the next node to visit. We may stop only whencurrreturns tostartafter at least one visit.
The statement is the loop invariant.
In the example:
[4], output is empty and [4] is the next node to visit.[4], output is [4] and [7] is the next node to visit.[7], output is [4, 7] and [9] is the next node to visit.[9], output is [4, 7, 9] and [4] is again the next node to visit.At that last point, curr == start. Since a visit has already happened, the single cycle is complete.
First handle the representation for an empty list:
1if head = null, return []For every nonempty list:
start = head.curr = start.curr by adding its value to the output.curr = curr.next.curr is back at start, stop.Do not test curr != null because a valid nonempty circular list never reaches null.
Do not begin with:
1while curr != headwhen curr starts at head. That condition is already false before the first visit, so it skips a one-node circle and every other nonempty circle.
Visit first, then test for the return to start.
1FUNCTION valuesOnce(head)
2 INPUT:
3 head: a node reference or null
4
5 Each node has:
6 value: stored value
7 next: reference to the next node
8
9 Precondition:
10 - head is null, or
11 - head belongs to a finite valid circular singly linked list.
12 In a nonempty valid list, following next references eventually
13 returns to head and does not encounter null.
14
15 RETURNS:
16 A new sequence containing each node value exactly once,
17 in forward order beginning at head.
18
19 MUTATION:
20 Does not modify head, any node, or any next reference.
21
221 output <- empty sequence
232 IF head = null
243 RETURN output
254 END IF
26
275 start <- head
286 curr <- start
29
307 REPEAT
318 append curr.value to output
329 curr <- curr.next
3310 UNTIL curr = start
34
3511 RETURN output
36END FUNCTIONREPEAT ... UNTIL runs its body before checking the condition. Its body runs at least once, which a nonempty circular list requires.
Use the original list:
1head -> [4] -> [7] -> [9] -> back to [4]| Pseudocode line | start | curr | output | Result |
|---|---|---|---|---|
| 1 | — | — | [] | Create an empty output sequence. |
| 2 | — | — | [] | Check whether head = null. It is not null. |
| 5 | [4] | — | [] | Record the starting node. |
| 6 | [4] | [4] | [] | Set the next node to visit. |
State 0 has head and start referring to [4], and [9].next referring to [4].
| Pseudocode line | start | curr | output | Result |
|---|---|---|---|---|
| 8 | [4] | [4] | [4] | Process value 4. |
| 9 | [4] | [7] | [4] | Advance one link from [4] to [7]. |
| 10 | [4] | [7] | [4] | [7] != [4], so repeat. |
State 1 has 4 processed and [7] next.
| Pseudocode line | start | curr | output | Result |
|---|---|---|---|---|
| 8 | [4] | [7] | [4, 7] | Process value 7. |
| 9 | [4] | [9] | [4, 7] | Advance one link from [7] to [9]. |
| 10 | [4] | [9] | [4, 7] | [9] != [4], so repeat. |
State 2 has 4 and 7 processed and [9] next.
| Pseudocode line | start | curr | output | Result |
|---|---|---|---|---|
| 8 | [4] | [9] | [4, 7, 9] | Process value 9. |
| 9 | [4] | [4] | [4, 7, 9] | Advance one link from [9] back to [4]. |
| 10 | [4] | [4] | [4, 7, 9] | curr = start, so stop. |
| 11 | [4] | [4] | [4, 7, 9] | Return the output. |
State 4 has curr returned to start after one or more visits.
The returned sequence is:
1[4, 7, 9]We show that valuesOnce returns each value exactly once for a finite valid circular list.
If head = null, line 2 is true. The algorithm returns the empty sequence at line 3.
The result is required because there are no nodes to visit.
Now consider a nonempty valid circular list.
At lines 5 and 6:
1start <- head
2curr <- startNo node has been visited yet, and output is empty.
So output contains exactly the nodes visited from start up to but not including curr: none. Also, curr is the next node to visit. The invariant holds before the first repetition.
Assume the invariant holds at the start of one repetition.
curr.value, so the next unvisited node is now included in output.curr through exactly one next reference.output contains all nodes visited from start up to, but not including, the new curr.curr is the next node to visit if traversal continues.One repetition preserves the invariant.
A finite valid circle with n nodes returns to start after exactly n advances from start.
The algorithm processes one node before each advance. Therefore, when line 10 first finds curr = start, it has processed exactly the n nodes in the circle, in forward order.
It stops at that first return to start, so it does not begin a second cycle and does not repeat any node.
For a nonempty finite valid circular list, the algorithm returns every node value exactly once in forward order. Together with the empty-list case, the algorithm is correct.
Suppose the circular list contains n nodes.
A complete traversal:
headnext reference per repetitionheadFor the example, there are three visits:
1visit 4
2visit 7
3visit 9Then the traversal returns to [4] and stops.
In general, the loop performs exactly n visits.
Each visit does constant work:
next referencecurr with startSo the work is:
1n repetitions × O(1) work per repetition = O(n) timeThe algorithm stores only:
startcurrIgnoring the returned output collection, start and curr use constant auxiliary space:
1O(1) auxiliary spaceIf the output sequence is counted, it contains n values and uses O(n) space.
Incorrect condition:
1while curr != nullSmallest exposing input:
1[4] -> [7] -> back to [4]Wrong state:
1curr: [4] -> [7] -> [4] -> [7] -> ...curr never becomes null, so traversal never terminates.
Correction:
1Record start = head.
2Stop when curr returns to start after a visit.curr != head before visitingIncorrect structure:
1curr <- head
2while curr != head
3 append curr.value to output
4 curr <- curr.nextSmallest exposing input:
1head -> [5] -> back to [5]Wrong state at the first condition check:
1curr = head
2curr != head is falseThe loop body never runs, so the output is:
1[]But the correct output is:
1[5]Correction: use a visit-then-check structure such as REPEAT ... UNTIL curr = start.
Incorrect assumption:
1if head.next = head, the list is emptySmallest exposing input:
1head -> [5] -> back to [5]Wrong result:
1[]The value 5 is skipped even though the list contains one node.
Correction:
1The empty representation is head = null.
2head.next = head represents a valid one-node circle.| Input | Expected output | Reason |
|---|---|---|
head = null | [] | Empty list has no nodes. |
[5] -> back to [5] | [5] | Visit the one node once, then return to head. |
[4] -> [7] -> back to [4] | [4, 7] | Complete one cycle without repeating [4]. |
[4] -> [7] -> [9] -> back to [4] | [4, 7, 9] | Visit each node in forward order once. |
A nonempty chain ending in null | Not a valid input | A valid nonempty circular list has no null next reference. |
Implement:
1valuesOnce(head)Contract to satisfy:
head = null.next references.head = null, return [].curr is null.Executable tests verify:
1empty list -> []
2one-node circle -> its one value once
3three-node circle -> each value once in forward order1class Node:
2 def __init__(self, value):
3 self.value = value
4 self.next = None
5
6def make_circle(values):
7 nodes = [Node(v) for v in values]
8 for i, node in enumerate(nodes):
9 node.next = nodes[(i + 1) % len(nodes)] # last node points back to the first
10 return nodes[0] if nodes else None
11
12def values_once(head):
13 output = []
14 if head is None:
15 return output
16 start = head
17 curr = start
18 while True: # visit first, then test: REPEAT ... UNTIL
19 output.append(curr.value)
20 curr = curr.next
21 if curr is start:
22 break
23 return output
24
25print(values_once(make_circle([4, 7, 9])))
26print(values_once(make_circle([5])))
27print(values_once(make_circle([])))1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static class Node {
6 int value;
7 Node next;
8
9 Node(int value) {
10 this.value = value;
11 }
12 }
13
14 static Node makeCircle(int[] values) {
15 if (values.length == 0) return null;
16 Node[] nodes = new Node[values.length];
17 for (int i = 0; i < values.length; i++) nodes[i] = new Node(values[i]);
18 for (int i = 0; i < nodes.length; i++) {
19 nodes[i].next = nodes[(i + 1) % nodes.length]; // last node points back to the first
20 }
21 return nodes[0];
22 }
23
24 static List<Integer> valuesOnce(Node head) {
25 List<Integer> output = new ArrayList<>();
26 if (head == null) return output;
27 Node start = head;
28 Node curr = start;
29 do { // visit first, then test
30 output.add(curr.value);
31 curr = curr.next;
32 } while (curr != start);
33 return output;
34 }
35
36 public static void main(String[] args) {
37 System.out.println(valuesOnce(makeCircle(new int[]{4, 7, 9})));
38 System.out.println(valuesOnce(makeCircle(new int[]{5})));
39 System.out.println(valuesOnce(makeCircle(new int[]{})));
40 }
41}1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct Node {
6 int value;
7 Node* next;
8 Node(int v) : value(v), next(nullptr) {}
9};
10
11Node* makeCircle(const vector<int>& values) {
12 if (values.empty()) return nullptr;
13 vector<Node*> nodes;
14 for (int v : values) nodes.push_back(new Node(v));
15 for (size_t i = 0; i < nodes.size(); i++) {
16 nodes[i]->next = nodes[(i + 1) % nodes.size()]; // last node points back to the first
17 }
18 return nodes[0];
19}
20
21vector<int> valuesOnce(Node* head) {
22 vector<int> output;
23 if (head == nullptr) return output;
24 Node* start = head;
25 Node* curr = start;
26 do { // visit first, then test
27 output.push_back(curr->value);
28 curr = curr->next;
29 } while (curr != start);
30 return output;
31}
32
33void show(const vector<int>& v) {
34 cout << "[";
35 for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
36 cout << "]" << endl;
37}
38
39int main() {
40 show(valuesOnce(makeCircle({4, 7, 9})));
41 show(valuesOnce(makeCircle({5})));
42 show(valuesOnce(makeCircle({})));
43}1class Node {
2 constructor(value) {
3 this.value = value;
4 this.next = null;
5 }
6}
7
8function makeCircle(values) {
9 const nodes = values.map((v) => new Node(v));
10 nodes.forEach((node, i) => {
11 node.next = nodes[(i + 1) % nodes.length]; // last node points back to the first
12 });
13 return nodes.length ? nodes[0] : null;
14}
15
16function valuesOnce(head) {
17 const output = [];
18 if (head === null) return output;
19 const start = head;
20 let curr = start;
21 do { // visit first, then test
22 output.push(curr.value);
23 curr = curr.next;
24 } while (curr !== start);
25 return output;
26}
27
28const show = (v) => console.log(`[${v.join(', ')}]`);
29show(valuesOnce(makeCircle([4, 7, 9])));
30show(valuesOnce(makeCircle([5])));
31show(valuesOnce(makeCircle([])));In an ordinary singly linked list the last node's next is null. In a circular one it points back to the first node. That one change breaks the usual while curr != null loop, which would never end.
It is a circular list whose nodes also carry a prev reference. The last node's next points to the first, and the first node's prev points to the last. The circular singly case in this lesson has next links only.
A full traversal is O(n) time for n nodes, with O(1) auxiliary space, because each repetition does constant work and the loop runs exactly n times. The cost of other operations depends on the operation.
If curr starts at head, the condition is false before the first visit, so the body never runs and a one-node circle returns an empty result. Visit first, then test, as in REPEAT ... UNTIL curr = start.
No. A node whose next points to itself is a valid one-node circle, and traversal returns its value once. The empty circular list is head = null.