Java solutions for linked-list problems — reversing (iteratively and recursively), detecting a cycle and finding its start, merging K sorted lists, reversing in K-groups, removing the Nth node from the end, flattening a multilevel list, copying a list with random pointers, merge sort on a list, adding two numbers, list intersection, rotating and reordering a list — plus implementing LRU and LFU caches in O(1).
Published September 25, 2026
Linked-list problems are about pointer discipline. The standard tools:
Draw the pointers before coding, and test with 0, 1 and 2 nodes. All the solutions use:
class ListNode { int val; ListNode next; ListNode(int v) { val = v; } ListNode(int v, ListNode n) { val = v; next = n; } }
Short answer:
prev, cur, next). O(n) time, O(1) space.head.next.next = head and head.next = null. O(n) time, but O(n) stack space, so it risks a StackOverflowError on long lists.ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; }
return prev;
}
ListNode reverseRec(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseRec(head.next);
head.next.next = head; head.next = null;
return newHead;
}
Short answer:
slow moves 1 step and fast moves 2; if they meet, there's a cycle. O(n), O(1).ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
if (slow == fast) {
for (slow = head; slow != fast; slow = slow.next, fast = fast.next) { }
return slow;
}
}
return null;
}
Short answer:
next. O(N log K) for N nodes in total.ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode l : lists) if (l != null) pq.add(l);
ListNode dummy = new ListNode(0), tail = dummy;
while (!pq.isEmpty()) {
ListNode n = pq.poll(); tail.next = n; tail = n;
if (n.next != null) pq.add(n.next);
}
return dummy.next;
}
Learn it in depth → K-way Merge
Short answer: Check that k nodes remain; if not, leave them as they are. Otherwise reverse those k nodes in place, connect the previous group's tail to the new head, and continue. Use a dummy head. O(n), O(1).
ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head), groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) kth = kth.next;
if (kth == null) break;
ListNode groupNext = kth.next, prev = groupNext, cur = groupPrev.next;
while (cur != groupNext) { ListNode nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
ListNode oldFirst = groupPrev.next;
groupPrev.next = kth; groupPrev = oldFirst;
}
return dummy.next;
}
Short answer: Two pointers with a gap of n, starting from a dummy node (which handles removing the head): move fast n+1 steps ahead, then move both until fast is null. Then slow.next is the node to remove. One pass, O(1). (Practice)
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head), fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = fast.next;
while (fast != null) { fast = fast.next; slow = slow.next; }
slow.next = slow.next.next;
return dummy.next;
}
Short answer: Each node may have a child list. Flatten depth-first, so each child list comes right after its parent: when a node has a child, find the child list's tail, splice node → child … tail → node.next, fix the prev pointers, and set child = null. Continue from node.next. O(n), iteratively with O(1) space. (Alternatively, use a stack or recursion.)
Node flatten(Node head) {
for (Node cur = head; cur != null; cur = cur.next) {
if (cur.child == null) continue;
Node tail = cur.child;
while (tail.next != null) tail = tail.next;
tail.next = cur.next;
if (cur.next != null) cur.next.prev = tail;
cur.next = cur.child; cur.child.prev = cur; cur.child = null;
}
return head;
}
Short answer: Use a HashMap plus a doubly linked list: the map gives O(1) lookup of nodes; the list keeps the recency order (most recent at the head). get moves the node to the head; put inserts or updates at the head, and evicts the tail when over capacity. O(1) for each operation. (LRU Cache)
LinkedHashMap with accessOrder=true, overriding removeEldestEntry (not thread-safe), or Caffeine (concurrent, and its Window TinyLFU policy has better hit rates).class LRUCache {
private final int cap; private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0), tail = new Node(0, 0);
static class Node { int key, val; Node prev, next; Node(int k, int v) { key = k; val = v; } }
LRUCache(int capacity) { cap = capacity; head.next = tail; tail.prev = head; }
public int get(int key) {
Node n = map.get(key); if (n == null) return -1;
unlink(n); addFront(n); return n.val;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) { n.val = value; unlink(n); addFront(n); return; }
if (map.size() == cap) { Node lru = tail.prev; unlink(lru); map.remove(lru.key); }
n = new Node(key, value); map.put(key, n); addFront(n);
}
private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
}
Short answer:
A → A' → B → B');copy.random = orig.random.next;Node copyRandomList(Node head) {
for (Node c = head; c != null; c = c.next.next) c.next = new Node(c.val, c.next);
for (Node c = head; c != null; c = c.next.next) if (c.random != null) c.next.random = c.random.next;
Node dummy = new Node(0), t = dummy;
for (Node c = head; c != null; c = c.next) { t.next = c.next; t = t.next; c.next = c.next.next; }
return dummy.next;
}
Short answer: Merge sort suits lists: there's no random access, and merging needs no extra arrays. Find the middle with slow and fast pointers, split, sort each half recursively, then merge. O(n log n) time; O(log n) stack space (a bottom-up iterative version achieves O(1)).
ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
ListNode right = slow.next; slow.next = null;
return merge(sortList(head), sortList(right));
}
ListNode merge(ListNode a, ListNode b) {
ListNode d = new ListNode(0), t = d;
while (a != null && b != null) { if (a.val <= b.val) { t.next = a; a = a.next; } else { t.next = b; b = b.next; } t = t.next; }
t.next = a != null ? a : b;
return d.next;
}
Short answer:
ListNode addTwoNumbers(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), t = dummy; int carry = 0;
while (a != null || b != null || carry != 0) {
int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
carry = sum / 10; t.next = new ListNode(sum % 10); t = t.next;
if (a != null) a = a.next; if (b != null) b = b.next;
}
return dummy.next;
}
Short answer: Use two pointers that switch heads: when pointer A reaches the end, it continues from head B, and vice versa. Both travel lenA + lenB, so they meet at the intersection (or both become null). O(m + n), O(1). (Alternative: compute both lengths, then align the starts.)
ListNode getIntersectionNode(ListNode a, ListNode b) {
ListNode p = a, q = b;
while (p != q) { p = p == null ? b : p.next; q = q == null ? a : q.next; }
return p;
}
Short answer:
tail.next = head).k %= len.len - k - 1: break the ring after it.O(n), O(1).
ListNode rotateRight(ListNode head, int k) {
if (head == null) return null;
int len = 1; ListNode tail = head;
while (tail.next != null) { tail = tail.next; len++; }
tail.next = head;
for (int i = 0; i < len - k % len; i++) tail = tail.next;
ListNode newHead = tail.next; tail.next = null;
return newHead;
}
Short answer: Three steps, O(n) time and O(1) space:
void reorderList(ListNode head) {
if (head == null) return;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
ListNode second = reverse(slow.next); slow.next = null;
for (ListNode first = head; second != null; ) {
ListNode n1 = first.next, n2 = second.next;
first.next = second; second.next = n1;
first = n1; second = n2;
}
}
Short answer: Evict the least frequently used key, breaking ties by least recent use. For O(1) operations:
keyToNode (value and frequency);freqToList (a LinkedHashSet or doubly linked list of keys per frequency, in recency order);minFreq counter.On get and put, increment the key's frequency: move it from list f to list f+1, and if list f was the minimum and is now empty, minFreq++. On insert, set minFreq = 1. Evict the oldest key in freqToList[minFreq].
class LFUCache {
private final int cap; private int minFreq;
private final Map<Integer, int[]> vals = new HashMap<>(); // key -> {value, freq}
private final Map<Integer, LinkedHashSet<Integer>> byFreq = new HashMap<>();
LFUCache(int capacity) { cap = capacity; }
public int get(int key) {
int[] e = vals.get(key); if (e == null) return -1;
touch(key, e); return e[0];
}
public void put(int key, int value) {
if (cap == 0) return;
int[] e = vals.get(key);
if (e != null) { e[0] = value; touch(key, e); return; }
if (vals.size() == cap) {
Iterator<Integer> it = byFreq.get(minFreq).iterator();
int evict = it.next(); it.remove(); vals.remove(evict);
}
vals.put(key, new int[]{value, 1}); minFreq = 1;
byFreq.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
}
private void touch(int key, int[] e) {
LinkedHashSet<Integer> set = byFreq.get(e[1]); set.remove(key);
if (set.isEmpty() && e[1] == minFreq) minFreq++;
e[1]++;
byFreq.computeIfAbsent(e[1], f -> new LinkedHashSet<>()).add(key);
}
}
Q: Why use a dummy head node?
A: It gives every real node a predecessor, so inserting or deleting at the head needs no special case, and the result is simply dummy.next.
Q: How would you make the LRU cache thread-safe?
A: The simplest option is a lock around each operation (or Collections.synchronizedMap on a LinkedHashMap). For high concurrency, use Caffeine, which uses concurrent hash maps, lock-free buffers and batched policy updates.
Q: When is recursion a bad idea for linked lists? A: For long lists (hundreds of thousands of nodes), recursion depth equals the list length and can overflow the stack. Iterative versions use O(1) space.
Q: LRU or LFU: which evicts better? A: LRU adapts quickly to changing access patterns but is fooled by one-off scans; LFU keeps popular items but can hold stale ones. Modern caches such as Caffeine's W-TinyLFU combine recency and frequency.