How does one find a loop in a singly linked list in O(n) time using constant memory? You cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.).
Solution
I first figured this out when I was asked the question in a Microsoft interview, so there’s verification that one question in the book was from a real interview. The best part of this problem is that I actually needed to write the code out for it a little while ago to detect a bug.
One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there’s a loop.
Now for another puzzle.. I think the next question I had to answer was something along the lines of “OK, How do you remove a loop in a linked list with the same constraints?” The latter question definitely seems harder, but in the sequence of questions I’d already answered for the interviewer, the solution was pretty obvious. I’ll leave that solution to someone else today.
Hm. I think I should pick up that book. I’ve always wondered where people got their juicy interview riddles.. I’ve always just repeated ones I’ve heard before or made up new ones along the same lines.
2026 Update: Parity Invariants in Modern Software
The Last Ball puzzle demonstrates the power of invariant analysis: identify a property that is preserved through every operation, and you can determine the final state without simulating every step. This technique is directly applicable to algorithm correctness proofs and distributed systems.
The invariant technique in modern engineering:
Loop invariants — a property true before and after every iteration, used to prove algorithm correctness (QuickSort, binary search)
Transaction invariants — total balance never changes through valid payment operations
Protocol invariants — Raft consensus guarantees that committed entries are never lost, proven via a leader completeness invariant
The XOR coding version (asked in 2026):
def final_value(arr):
"""
Pick any two numbers, remove them, add their XOR back.
What is the final number?
Invariant: XOR of all elements never changes.
"""
result = 0
for x in arr:
result ^= x
return result
print(final_value([3, 5, 7])) # 3^5^7 = 1, regardless of operation order
Still asked at (2026): Google (for algorithmic reasoning), Jane Street (for invariant-based proofs), and any role where formal reasoning about system correctness is required.
💡Strategies for Solving This Problem
Linked List Operations
This is a general linked list problem that usually asks you to implement common operations. Let me cover the most frequently asked ones.
Common Operations
1. Insertion: Beginning, end, at position
2. Deletion: By value, at position
3. Search: Find node by value
4. Reverse: Covered in other problems
5. Find middle: Slow/fast pointer
6. Detect cycle: Covered separately
The Dummy Node Trick
Use a dummy node at the start to simplify edge cases. Makes insertion/deletion code cleaner because you never need to update head pointer directly.
The Two-Pointer Patterns
Find middle: Slow moves 1 step, fast moves 2. When fast reaches end, slow is at middle.
Nth from end: Move fast n steps ahead, then move both until fast reaches end.
Cycle detection: If fast ever equals slow, there's a cycle.
What Interviewers Look For
Handling null/empty lists
Not losing references (causing memory leaks)
Edge cases: single node, two nodes
Clean code without lots of special cases
At Various Companies
Every company asks linked list questions. They're fundamental. The key is knowing the patterns (dummy node, two pointers, recursion) and applying them cleanly.
Most common: "Remove nth node from end" (fast/slow pointers), "Merge two sorted lists" (like merge sort), "Find intersection of two lists" (length difference trick).
✅Solution
Solution: Common Linked List Operations
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// Insert at beginning - O(1)
insertAtHead(val) {
const newNode = new ListNode(val);
newNode.next = this.head;
this.head = newNode;
this.size++;
}
// Insert at end - O(n)
insertAtTail(val) {
const newNode = new ListNode(val);
if (this.head === null) {
this.head = newNode;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
this.size++;
}
// Insert at position - O(n)
insertAt(val, index) {
if (index < 0 || index > this.size) return false;
if (index === 0) {
this.insertAtHead(val);
return true;
}
const newNode = new ListNode(val);
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
this.size++;
return true;
}
// Delete by value - O(n)
delete(val) {
if (this.head === null) return false;
// Delete head
if (this.head.val === val) {
this.head = this.head.next;
this.size--;
return true;
}
let current = this.head;
while (current.next !== null) {
if (current.next.val === val) {
current.next = current.next.next;
this.size--;
return true;
}
current = current.next;
}
return false; // Not found
}
// Delete at position - O(n)
deleteAt(index) {
if (index < 0 || index >= this.size) return false;
if (index === 0) {
this.head = this.head.next;
this.size--;
return true;
}
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
this.size--;
return true;
}
// Search - O(n)
find(val) {
let current = this.head;
let index = 0;
while (current !== null) {
if (current.val === val) return index;
current = current.next;
index++;
}
return -1; // Not found
}
// Find middle (fast/slow pointers) - O(n)
findMiddle() {
if (this.head === null) return null;
let slow = this.head;
let fast = this.head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// Find nth from end (two pointers) - O(n)
findNthFromEnd(n) {
if (n <= 0) return null;
let fast = this.head;
let slow = this.head;
// Move fast n steps ahead
for (let i = 0; i < n; i++) {
if (fast === null) return null; // n > length
fast = fast.next;
}
// Move both until fast reaches end
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
// Print list
print() {
const arr = [];
let current = this.head;
while (current !== null) {
arr.push(current.val);
current = current.next;
}
console.log(arr.join(" -> "));
}
// Get length
length() {
return this.size;
}
}
// Tests
const list = new LinkedList();
list.insertAtTail(1);
list.insertAtTail(2);
list.insertAtTail(3);
list.insertAtTail(4);
list.insertAtTail(5);
console.log("Original:");
list.print(); // 1 -> 2 -> 3 -> 4 -> 5
console.log("Middle:", list.findMiddle().val); // 3
console.log("2nd from end:", list.findNthFromEnd(2).val); // 4
list.insertAt(99, 2);
console.log("After insert at index 2:");
list.print(); // 1 -> 2 -> 99 -> 3 -> 4 -> 5
list.delete(99);
console.log("After delete 99:");
list.print(); // 1 -> 2 -> 3 -> 4 -> 5
console.log("Find 3:", list.find(3)); // 2 (index)
Useful Helper: Remove Nth From End
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0);
dummy.next = head;
let fast = dummy;
let slow = dummy;
// Move fast n+1 steps ahead
for (let i = 0; i <= n; i++) {
if (fast === null) return head; // n too large
fast = fast.next;
}
// Move both until fast reaches end
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
// Remove node
slow.next = slow.next.next;
return dummy.next;
}
Useful Helper: Merge Two Sorted Lists
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// Attach remaining
current.next = l1 !== null ? l1 : l2;
return dummy.next;
}
Complexity Summary
Operation
Time
Notes
Insert at head
O(1)
Always fast
Insert at tail
O(n)
Need to traverse (use tail pointer for O(1))
Insert at position
O(n)
Need to traverse
Delete
O(n)
Need to find node
Search
O(n)
Linear scan
Find middle
O(n)
Fast/slow pointers
Nth from end
O(n)
Two-pointer trick
Common Patterns
Dummy node: Simplifies head operations
const dummy = new ListNode(0);
dummy.next = head;
// ... do operations ...
return dummy.next; // New head
Two pointers (fast/slow): Find middle, cycle detection
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// slow is at middle
Two pointers (gap): Nth from end
let slow = head, fast = head;
for (let i = 0; i < n; i++) fast = fast.next;
while (fast) {
slow = slow.next;
fast = fast.next;
}
// slow is nth from end
This site uses cookies for analytics and to display ads via Google AdSense. By continuing to use the site you consent to our use of cookies. See our Privacy Policy for details and opt-out links.
