Linked Lists

Linked list problems require manipulating node pointers directly — no random access, no indices — which makes the patterns distinct from array problems.

• Four sub-patterns cover every interview ask: fast/slow pointers for cycles and midpoints, in-place reversal, gap-based two pointers for N-from-end, and two-list merge/partition
• All operations are O(1) space by rewiring pointers instead of copying to arrays
• Reach for it when the problem involves cycles, reversals, merging sorted lists, reordering, or removing nodes at a relative position

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of linked list patterns.

Practice Tips

How to Identify a Fast & Slow Pointer Problem

• The problem involves a linked list with no random access
• You need to find a cycle, its start, or the middle of the list
• You need to remove or locate a node k positions from the end
• The problem asks you to restructure, reorder, or palindrome-check a list in O(1) space

Fast & Slow vs. Other Techniques

Interview Approach

1. Draw 3-5 nodes on paper and trace the pointers — do this before coding
2. Pick the right variant: while (fast != null && fast.next != null) for second-middle; while (fast.next != null && fast.next.next != null) for first-middle
3. When the list is modified (reverse, merge, partition), always use a dummy node so the head never needs special handling
4. Before returning, verify the tail is null-terminated — forgetting this creates cycles
5. State the three steps out loud for multi-step problems (find middle, reverse, merge) before writing any code

4 Main Patterns

Pattern 1: Fast & Slow (Cycle / Middle)

Copy// slow moves 1 step, fast moves 2 — they meet inside a cycle or fast exits at the end
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
        /* cycle detected */
    }
}
// if no cycle: slow is at the second middle (or only middle for odd length)

Pattern 2: In-Place List Reversal

Copy// three-pointer walk — O(1) space, rewires links as it goes
ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;  // save
    curr.next = prev;           // reverse
    prev = curr;                // advance
    curr = next;
}
return prev; // new head

Pattern 3: Gap-Based Two Pointers (N from End)

Copy// advance first n+1 steps; then move together — second stops before the target
ListNode dummy = new ListNode(0);
dummy.next = head;

ListNode first = dummy, second = dummy;

for (int i = 0; i <= n; i++) {
    first = first.next;  // gap of n+1
}

while (first != null) { 
    first = first.next; 
    second = second.next; 
}
second.next = second.next.next; // delete target

Pattern 4: Two-List Merge / Partition

Copy// dummy node per list avoids head-change edge cases
ListNode dummyA = new ListNode(0), dummyB = new ListNode(0);
ListNode a = dummyA, b = dummyB;

while (head != null) {
    if (condition(head)) { 
        a.next = head; 
        a = a.next;
    } else { 
        b.next = head; 
        b = b.next; 
    }
    head = head.next;
}
b.next = null;       // must null-terminate to avoid cycle
a.next = dummyB.next;
return dummyA.next;

General Templates

ListNode Definition

Copypublic class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

Dummy Node Template

CopyListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
// ... modify list using prev ...
return dummy.next; // head may have changed

Problem 1: Linked List Cycle ⭐ MUST DO [B75-141]

Return the node where the cycle begins. Return null if no cycle.

Example:

CopyInput:  3 → 2 → 0 → -4 → (back to 2)
Output: node with value 2

Input:  1 → 2 → null
Output: null

Key Insight:

• Let F = distance from head to cycle start, C = cycle length, k = distance from cycle start to meeting point.
• When slow and fast meet: slow traveled F + k, fast traveled F + k + C (a full extra loop). Since fast = 2 × slow: F + k = C, so F = C - k.
• C - k is exactly the distance from the meeting point to the cycle start (going forward). So resetting one pointer to head and advancing both at speed 1 makes them meet at the cycle start.

Solution:

Copypublic 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) {
            ListNode finder = head;
            while (finder != slow) {
                finder = finder.next;
                slow = slow.next;
            }
            return finder; // cycle start
        }
    }
    return null;
}

Complexity:

Real World: Finding the exact module where a circular import begins — not just detecting the cycle but pinpointing the entry point so the developer knows which import to remove. Also used in garbage collectors to identify the root of a reference cycle.

Variations:

1. Detect only (no start needed) — return true as soon as slow == fast in phase 1; skip phase 2 entirely. This is the B75-141 ask.
2. Find cycle length — after meeting, keep one pointer fixed and advance the other until they meet again; count the steps.
3. Remove the cycle — once the start is found, walk to the node whose next points back to the start and set next = null. One extra pass after this algorithm.

Interview Disguises:

• "A dependency resolver finds a circular import chain. Return the exact module where the cycle begins so the developer can break it." — cycle start detection; the F = C - k insight is the key.
• "A garbage collector traces object references and finds a reference cycle. Return the first object in the cycle — the one that anchors it — so it can be freed." — linked list cycle II; objects are nodes, references are next pointers.

Problem 2: Merge Two Sorted Lists ⭐ MUST DO [B75-21]

Merge two sorted linked lists and return the merged list.

Example:

CopyInput:  l1 = [1, 2, 4],  l2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]

Solution:

Copypublic ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1; l1 = l1.next;
        }
        else {
            curr.next = l2; l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Complexity:

Real World: Merging two sorted result sets from different database shards without loading both fully into memory — a common operation in distributed query engines. Also the core subroutine in merge sort (Problem 11 uses it directly).

Variations:

1. Merge K sorted lists — use a min-heap of size K to always pick the smallest head; call this merge as a subroutine or use divide-and-conquer pairing. Covered in the heap guide.
2. Merge two sorted lists recursively — elegant one-liner but costs O(n + m) call stack space vs O(1) here; worth knowing as a contrast to show why iterative is preferred.

Interview Disguises:

• "Two database shards each return query results as sorted linked lists. Merge them into a single sorted stream for the client without buffering both lists in memory." — merge two sorted lists; rows are nodes, sorted by key.
• "Two servers write sorted event logs independently. Merge both logs into a single chronological stream." — same dummy-node merge; events are nodes, timestamps are the comparison key.

Problem 3: Reverse Linked List ⭐ MUST DO [B75-206]

Reverse the nodes of the list from position left to right in one pass.

Example:

CopyInput:  [1, 2, 3, 4, 5],  left = 2,  right = 4
Output: [1, 4, 3, 2, 5]

Input:  [1, 2, 3, 4, 5],  left = 1,  right = 5
Output: [5, 4, 3, 2, 1]

Key Insight:

• If you only need to reverse the whole list, the simpler three-pointer walk suffices — that is the B75-206 ask. See Variation 1.
• Front-insertion trick for partial reversal: keep prev pointing to the node before the reversal zone, and tail pointing to what started as the left node (it becomes the tail of the reversed section).
• Each iteration, detach the node just after tail, reattach it right after prev. Repeat right - left times.
• This avoids splitting and rejoining the list.

Solution:

Copypublic ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;

    for (int i = 1; i < left; i++) {
        prev = prev.next;  // stop before zone
    }

    ListNode tail = prev.next;  // left node; becomes tail after reversal
    for (int i = 0; i < right - left; i++) {
        ListNode next = tail.next;
        tail.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }

    return dummy.next;
}

Complexity:

Real World: Undoing a batch of operations between steps L and R in a transaction log without touching earlier or later history. Also used in animation systems to play a segment of a keyframe sequence backwards.

Variations:

1. Reverse whole list — simpler three-pointer walk: prev=null, curr=head, advance until done. This is the B75-206 ask.
2. Reverse in groups of k (LC 25) — apply the front-insertion trick every k nodes; connect each reversed group's tail to the next group's head.
3. Reverse alternate groups — reverse k nodes, skip k nodes, repeat. Combine the front-insertion trick with a skip counter.

Interview Disguises:

• "A transaction log stores operations as a linked list. Reverse only the operations between positions L and R to undo that batch without affecting the rest of the log." — reverse linked list II; the range [left, right] is the batch.
• "An animation timeline stores keyframes as nodes. Reverse the segment between frame L and frame R to play that section backwards while keeping the rest of the timeline intact." — subrange reversal with front-insertion; keyframes are nodes.

Problem 4: Palindrome Linked List ⭐ MUST DO

Check if a linked list is a palindrome in O(n) time and O(1) space.

Example:

CopyInput:  [1, 2, 2, 1]  →  true
Input:  [1, 2, 3, 2, 1]  →  true
Input:  [1, 2]  →  false

Key Insight:

• Three steps: find the middle (fast/slow), reverse the second half in place, then compare the two halves node by node.
• For odd-length lists the middle node belongs to neither half — comparing stops when the reversed pointer reaches null, so it is naturally skipped.

Solution:

Copypublic boolean isPalindrome(ListNode head) {
    // Step 1: find middle (second middle for even length)
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Step 2: reverse second half
    ListNode secondHalf = reverse(slow);

    // Step 3: compare
    ListNode left = head, right = secondHalf;
    while (right != null) {
        if (left.val != right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
}

private ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Complexity:

Real World: Validating symmetric data sequences in memory-constrained systems — e.g., checking if a DNA base sequence reads the same in both directions for restriction enzyme recognition, without copying the sequence to an array.

Variations:

1. Return the node where palindrome breaks — instead of returning true/false, return the first mismatching node. Same three steps; change the compare loop to return the node instead of false.

Interview Disguises:

• "A DNA sequence is stored as a linked list of base characters. Check if it is palindromic (reads the same forwards and backwards) in O(1) space without converting to an array." — palindrome linked list; DNA bases are node values.
• "A streaming validator checks if a received packet sequence is symmetric as a data integrity check, using no extra buffer memory." — find middle, reverse second half, compare = palindrome check on a stream.

Problem 5: Remove N-th Node From End ⭐ MUST DO [B75-19]

Remove the n-th node from the end of the list in one pass.

Example:

CopyInput:  [1, 2, 3, 4, 5],  n = 2
Output: [1, 2, 3, 5]

Input:  [1],  n = 1
Output: []

Key Insight:

• Advance first by n+1 steps (not n) so second lands on the node before the target, enabling deletion via second.next = second.next.next.
• A dummy node absorbs the edge case where the head itself is removed (n = list length).

Solution:

Copypublic ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy, second = dummy;

    for (int i = 0; i <= n; i++) {
        first = first.next; // gap of n+1
    }

    while (first != null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
}

Complexity:

Real World: Evicting the oldest entry from a fixed-size sliding window cache implemented as a linked list — the N-th node from the end is the boundary of the window. Also used in log rotation to remove the entry that falls outside the retention window.

Variations:

1. Return the N-th node from end without deleting — same gap technique; just return second.next instead of unlinking it. Useful as a building block.
2. Remove all nodes at positions divisible by k from the end — generalize: run the gap technique with gap = k, removing each target; repeat or adapt the loop condition.

Interview Disguises:

• "A fixed-size activity log keeps the last N user actions as a linked list. Remove the entry that just fell outside the retention window — the N-th from the end — in a single pass." — remove Nth from end; log entries are nodes.
• "A network buffer enforces a maximum depth. Drop the packet that is exactly N positions from the tail of the queue in one traversal." — gap-based two pointers with dummy node; packets are nodes.

Problem 6: Intersection of Two Linked Lists

Return the node where two linked lists intersect, or null if they don't.

Example:

CopylistA: 4 → 1 → 8 → 4 → 5
listB:      5 → 6 → 1 → 8 → 4 → 5
                         ↑ intersection at node 8
Output: node with value 8

Key Insight:

• If the two lists have lengths A and B, a pointer starting at headA and switching to headB when it reaches null traverses A + B total nodes. Same for the other direction. Both pointers arrive at the intersection (or null) after A + B steps.
• No length calculation needed — the switch automatically equalizes the paths.

Solution:

Copypublic ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a; // intersection node or null
}

Complexity:

Real World: Finding the first shared dependency where two service dependency chains converge — e.g., both service A's chain and service B's chain eventually depend on the same shared library node. Also used in version control to find the merge base of two branches.

Variations:

1. Detect intersection without the A+B equalization trick — compare tail nodes: if both lists end at the same node, they intersect; then use length difference to find the exact node. Same O(n+m) time, more explicit.
2. Find all intersection nodes — if the lists share a suffix of k nodes, return all k nodes. Walk from the intersection node to the end of both lists together.

Interview Disguises:

• "Two microservices each have a chain of middleware layers stored as a linked list. Find the first shared middleware component where both chains converge." — intersection of two linked lists; middleware layers are nodes.
• "Two Git branches diverged from a common commit. Find the exact commit where they first shared history — the merge base." — two linked lists merging at a common node; commits are nodes, parent pointers are next.

Problem 7: Remove Duplicates from Sorted List II

Remove all nodes that have duplicate numbers, leaving only distinct values.

Example:

CopyInput:  [1, 2, 3, 3, 4, 4, 5]
Output: [1, 2, 5]

Input:  [1, 1, 1, 2, 3]
Output: [2, 3]

Key Insight:

• Use prev to track the last confirmed unique node. When duplicates are found, advance through the whole group then connect prev directly past it.
• Only advance prev when no duplicates were found at curr.

Solution:

Copypublic ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;

    while (head != null) {
        if (head.next != null && head.val == head.next.val) {
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            prev.next = head.next; // skip entire group
        } else {
            prev = prev.next;      // unique node, advance prev
        }
        head = head.next;
    }

    return dummy.next;
}

Complexity:

Real World: Deduplicating a sorted audit log where any event appearing more than once is flagged as potentially tampered and must be removed entirely — stricter than keeping one copy. Also used in data pipelines to discard unreliable repeated sensor readings.

Variations:

1. Remove Duplicates I — keep one copy of each value instead of removing all. Simpler: use a single curr pointer and skip curr.next while values match; no dummy node needed.
2. Remove all nodes with a specific target value — same prev/skip structure; change the duplicate-detection condition to head.val == target. The dummy node handles the case where the head is the target.

Interview Disguises:

• "A sorted audit log treats any event code appearing more than once as tampered. Remove every occurrence of any repeated event code, leaving only codes that appear exactly once." — remove duplicates II; event codes are node values.
• "A sorted sensor stream discards any reading that appears more than once as a measurement glitch — remove all copies of glitched values, not just the extras." — same prev-skips-entire-group logic; sensor readings are node values.

Problem 8: Odd Even Linked List

Group all odd-index nodes first, then even-index nodes. Preserve relative order within each group. Indexing starts at 1.

Example:

CopyInput:  [1, 2, 3, 4, 5]
Output: [1, 3, 5, 2, 4]

Input:  [2, 1, 3, 5, 6, 4, 7]
Output: [2, 3, 6, 7, 1, 5, 4]

Key Insight:

• Two pointers odd and even advance together, each skipping over the other's group.
• Save evenHead at the start; connect the odd tail to it at the end.

Solution:

Copypublic ListNode oddEvenList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode odd = head, even = head.next, evenHead = even;

    while (even != null && even.next != null) {
        odd.next = even.next;   // odd skips over even
        odd = odd.next;
        even.next = odd.next;   // even skips over new odd
        even = even.next;
    }

    odd.next = evenHead;        // connect tails
    return head;
}

Complexity:

Real World: Reorganizing a task queue so all high-priority tasks (odd-indexed positions) run before low-priority ones (even-indexed), preserving arrival order within each group. Also used in memory layout optimization to group related objects by access pattern.

Variations:

1. Group by value parity instead of index parity — nodes with odd values first, even values second. Same two-pointer advance structure; change the condition from index tracking to node.val % 2 != 0.
2. Group into k buckets by index mod k — generalize from 2 groups to k groups using k dummy-headed lists; connect them in order at the end. The Partition List pattern generalizes this further.

Interview Disguises:

• "A print queue stores jobs as a linked list. Reorganize it so all odd-numbered jobs (by queue position) execute first, then even-numbered, without changing relative order within each group." — odd even list; jobs are nodes, positions are indices.
• "A playlist mixes tracks from two sources: odd positions are from source A, even from source B. Separate it so all source A tracks come first, then source B, preserving each source's order." — index-based partition into two groups = odd even list.

Problem 9: Partition List

Partition the list so all nodes with value < x come before nodes with value ≥ x, preserving relative order.

Example:

CopyInput:  [1, 4, 3, 2, 5, 2],  x = 3
Output: [1, 2, 2, 4, 3, 5]

Key Insight:

• Two dummy-headed lists collect the two groups separately. Route each node based on its value, then connect the less tail to the greater head.
• Null-terminate the greater list — its tail still points into the original list, which would create a cycle.

Solution:

Copypublic ListNode partition(ListNode head, int x) {
    ListNode lessHead = new ListNode(0), greaterHead = new ListNode(0);
    ListNode less = lessHead, greater = greaterHead;

    while (head != null) {
        if (head.val < x) {
            less.next = head;    less = less.next;
        }
        else {
            greater.next = head;  greater = greater.next;
        }
        head = head.next;
    }

    greater.next = null;        // must null-terminate to avoid cycle
    less.next = greaterHead.next;
    return lessHead.next;
}

Complexity:

Real World: A job scheduler separates a task queue into fast-lane (processing time < threshold) and slow-lane (processing time ≥ threshold) while preserving the arrival order of tasks within each lane. Also used in network routers to split packets into priority queues.

Variations:

1. Partition into three groups (< x, == x, > x) — add a third dummy-headed list for equal values; connect all three (less → equal → greater) at the end. Same pattern, one more list.

Interview Disguises:

• "A job scheduler stores tasks by estimated runtime. Move all tasks under a time threshold to the front of the queue for the fast worker, preserving their relative order." — partition list; tasks are nodes, threshold is x.
• "A network router splits incoming packets into a priority lane (size < limit) and a standard lane (size ≥ limit) while preserving packet arrival order within each lane." — two dummy lists routed by value; packets are nodes.

Problem 10: Reorder List ⭐ MUST DO [B75-143]

Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … in place.

Example:

CopyInput:  [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Input:  [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]

Key Insight:

• Three steps: (1) find the first middle using fast.next != null && fast.next.next != null — this keeps the first half equal or one node longer, (2) reverse the second half starting at slow.next, (3) interleave merge — alternate links from front and back, saving next pointers before relinking.
• The merge loop runs until second is null; any leftover node in first is already correctly placed.

Solution:

Copypublic void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }

    // Step 1: find first middle
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Step 2: reverse second half
    ListNode second = reverse(slow.next);
    slow.next = null;           // split the list

    // Step 3: interleave merge
    ListNode first = head;
    while (second != null) {
        ListNode tmp1 = first.next, tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

private ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Complexity:

Real World: Interleaving the two halves of a data stream — used in audio processing to interleave left-channel and right-channel samples stored sequentially in a single linked buffer. Also used in card shuffling algorithms (perfect riffle shuffle).

Variations:

1. Interleave two separate lists — skip Step 1 (no middle to find); go straight to the interleave merge of two already-separated lists. Simpler version that shows the merge step in isolation.
2. Reverse the second half and append — stop after Step 2 (find middle + reverse); connect the reversed second half to the end of the first. Produces a different reordering — useful for contrast.

Interview Disguises:

• "An audio codec stores left-channel samples followed by right-channel samples sequentially in a linked list. Interleave them so samples alternate L-R-L-R in a single pass." — reorder list; samples are nodes, first half is left channel, second half is right channel.
• "A card dealer stores a full deck as a linked list split into two halves. Perform a perfect riffle shuffle — alternate one card from each half — in place." — find middle, reverse second half, interleave merge = reorder list.

Problem 11: Sort List

Sort a linked list in O(n log n) time.

Example:

CopyInput:  [4, 2, 1, 3]
Output: [1, 2, 3, 4]

Key Insight:

• Merge sort is the natural fit — finding the middle (fast/slow) splits the list in O(n), and merging two sorted lists is O(n).
• Unlike arrays, linked lists don't need auxiliary space to merge — just rewire pointers. Space cost is O(log n) for the recursion stack only.

Solution:

Copypublic ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    // Find first middle and split
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null; // split into two halves

    ListNode left = sortList(head);
    ListNode right = sortList(slow);
    return merge(left, right);
}

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1; l1 = l1.next;
        }
        else {
            curr.next = l2; l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Complexity:

Real World: Sorting a large dataset that doesn't fit in memory — external merge sort on disk uses the same split-and-merge structure, just with file chunks instead of list halves. Also used in database engines to sort records returned as a cursor (linked list of rows).

Variations:

1. Bottom-up merge sort — instead of recursing, iteratively merge sublists of size 1, then 2, then 4. Eliminates the O(log n) recursion stack, achieving true O(1) space. Harder to implement but optimal.

Interview Disguises:

• "A memory-constrained embedded system needs to sort a linked list of sensor records. It cannot convert to an array. Sort in O(n log n) without allocating extra node storage." — sort list; merge sort is the only comparison sort that achieves O(n log n) on a linked list without O(n) extra space.
• "A database cursor returns rows as a linked list in arbitrary order. Sort them by key in O(n log n) time for a subsequent merge join with another sorted cursor." — merge sort on linked list; rows are nodes, sort key drives the merge comparison.

Problem 12: LFU Cache with TTL ⭐ MUST DO

Design a Least Frequently Used (LFU) cache that also expires entries after a TTL (time-to-live). get(key, currentTime) returns the value or -1 if the key is missing or expired. put(key, val, ttlMs, currentTime) inserts with a TTL in milliseconds. Expired entries are removed lazily on access and proactively via a periodic sweep.

Example:

CopyLFUCacheWithTTL cache = new LFUCacheWithTTL(2);
cache.put(1, 10, 500, 0);   // key=1, val=10, expires at t=500
cache.put(2, 20, 500, 0);   // key=2, val=20, expires at t=500
cache.get(1, 0);             // → 10  (freq[1]=2, freq[2]=1)
cache.put(3, 30, 500, 1);   // cache full — evict key=2 (LFU, lowest freq)
cache.get(2, 1);             // → -1  (evicted)
cache.get(1, 600);           // → -1  (expired — TTL elapsed)

Why a doubly linked list? A doubly linked list is the only structure that gives O(1) arbitrary removal and O(1) insertion at any position simultaneously. Arrays shift on removal — O(n). Heaps support O(1) peek but O(log n) arbitrary removal. BSTs are O(log n) for both. The linked list rewires in O(1) because each node holds direct pointers to its neighbors — no searching needed.

The HashMap completes the picture: it gives you the node pointer directly, so the list never has to search. The map handles lookup, the list handles rewiring — neither works without the other.

Key Insight:

• LFU eviction picks the least-frequently-used key. Ties break by LRU within the same frequency bucket, so each bucket is a mini LRU list (doubly linked list, newest at head, LRU at tail).
• On every get or put, promote the accessed node: remove from bucket[freq], increment freq, add to head of bucket[freq+1]. Track minFreq — it resets to 1 only when a brand-new key is inserted.
• TTL is stored as an absolute expiry timestamp (currentTime + ttlMs). Passing currentTime in (instead of calling the wall clock internally) makes the cache fully testable. Lazy expiry: check in get. Active expiry: a second sorted-by-expiry linked list lets sweepExpired() stop at the first non-expired node — O(expired) not O(capacity).
• On eviction, if the front of the sorted expiry list is already expired, take it instead of the LFU victim — O(1) expired-first check using the sorted list head.
• Each node lives in two doubly linked lists simultaneously: its frequency bucket list and the expiry list. This dual-intrusive-list design is why the node needs four link pointers (prev/next for the freq bucket, ePrev/eNext for the expiry list). It is the same design used in Caffeine (Java) and Guava production caches.

Solution:

Copyimport java.util.*;

class LFUCacheWithTTL {

    // ── Node lives in TWO intrusive doubly-linked lists simultaneously:
    //    1. A FreqBucket (LRU list for its frequency level)   ← dummy node anchor + arbitrary removal
    //    2. The ExpiryList (sorted ascending by expiry time)  ← sorted merge insert + arbitrary removal + sweep
    private static class Node {
        int key, val, freq;
        long expiry;           // absolute timestamp; 0 = no expiry
        Node prev, next;       // FreqBucket list links
        Node ePrev, eNext;     // ExpiryList links

        Node(int k, int v, long exp) { key = k; val = v; freq = 1; expiry = exp; }

        boolean isExpired(long currentTime) {
            return expiry != 0 && currentTime >= expiry;
        }
    }

    // ── FreqBucket: one doubly-linked list per frequency level.
    //    This is essentially a standalone LRU cache — newest at head, LRU at tail,
    //    O(1) insert at head, O(1) arbitrary removal, O(1) evict from tail.
    //    LFU is built by stacking N of these: one per frequency level.
    //    Dummy head + dummy tail make every operation branchless (no null checks on neighbors).
    //    Pattern: dummy node anchor + arbitrary node removal
    private static class FreqBucket {
        Node head, tail;   // sentinels — never hold real data
        int size;

        FreqBucket() {
            head = new Node(0, 0, 0);   // dummy head absorbs edge cases (empty list, head deletion)
            tail = new Node(0, 0, 0);   // dummy tail
            head.next = tail;
            tail.prev = head;
        }

        // Add node just after dummy head (MRU position)
        void addHead(Node n) {
            n.next = head.next;
            n.prev = head;
            head.next.prev = n;
            head.next = n;
            size++;
        }

        // Arbitrary node removal — O(1) because node holds its own prev/next.
        // Guard against double-remove; null out links so callers can detect removed state.
        void remove(Node n) {
            if (n.prev == null || n.next == null) {
                return;   // already removed — defensive guard
            }
            n.prev.next = n.next;
            n.next.prev = n.prev;
            n.prev = null;   // mark as removed so double-remove is a safe no-op
            n.next = null;
            size--;
        }

        // Peek at LRU tail without removing — caller removes via evict()
        Node peekLRU() {
            return isEmpty() ? null : tail.prev;   // dummy tail makes this safe even for size=1
        }

        boolean isEmpty() { return size == 0; }
    }

    // ── ExpiryList: a single doubly-linked list sorted ascending by expiry time.
    //    insertSorted: same pointer rewiring as merging into a sorted list.
    //    Pattern: sorted merge insert + arbitrary node removal
    private static class ExpiryList {
        Node head, tail;   // sentinels

        ExpiryList() {
            head = new Node(0, 0, 0);
            tail = new Node(0, 0, Long.MAX_VALUE);  // sentinel expiry = ∞
            head.eNext = tail;
            tail.ePrev = head;
        }

        // Sorted insert — walk until the right position,
        // then splice in exactly like linking two sorted lists at a merge point.
        void insertSorted(Node n) {
            Node cur = head.eNext;
            while (cur != tail && cur.expiry <= n.expiry) {
                cur = cur.eNext;
            }
            n.eNext = cur;
            n.ePrev = cur.ePrev;
            cur.ePrev.eNext = n;
            cur.ePrev = n;
        }

        // Arbitrary node removal — O(1) using node's own ePrev/eNext pointers.
        // Guard + null-out prevent double-remove.
        void remove(Node n) {
            if (n.ePrev == null || n.eNext == null) {
                return;   // already removed — defensive guard
            }
            n.ePrev.eNext = n.eNext;
            n.eNext.ePrev = n.ePrev;
            n.ePrev = null;   // mark as removed
            n.eNext = null;
        }

        // Peek at the soonest-to-expire node — O(1) check for expired-first eviction
        Node peekFront() {
            Node front = head.eNext;
            return (front == tail) ? null : front;
        }
    }

    // ── LFU internals
    private final int capacity;
    private int minFreq;
    private final Map<Integer, Node> map;             // key → Node
    private final Map<Integer, FreqBucket> buckets;   // freq → FreqBucket
    private final ExpiryList expiryList;

    public LFUCacheWithTTL(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.buckets = new HashMap<>();
        this.expiryList = new ExpiryList();
    }

    // currentTime passed in — caller controls the clock, making this fully testable
    public int get(int key, long currentTime) {
        Node n = map.get(key);
        if (n == null) {
            return -1;
        }
        if (n.isExpired(currentTime)) {
            evict(n);   // lazy expiry — single evict() handles all three structures
            return -1;
        }
        promote(n);   // increment frequency, move to next bucket
        return n.val;
    }

    // currentTime passed in — caller controls the clock, making this fully testable
    public void put(int key, int val, long ttlMs, long currentTime) {
        if (capacity <= 0) {
            return;
        }
        long expiry = (ttlMs > 0) ? currentTime + ttlMs : 0;
        if (map.containsKey(key)) {
            Node n = map.get(key);
            if (n.isExpired(currentTime)) {
                evict(n);   // treat expired key as a new insert — evict first, fall through
            } else {
                n.val = val;
                n.expiry = expiry;
                expiryList.remove(n);
                if (expiry != 0) {
                    expiryList.insertSorted(n);   // re-insert at correct sorted position
                }
                promote(n);
                return;
            }
        }
        if (map.size() >= capacity) {
            evictLFU(currentTime);
        }
        Node n = new Node(key, val, expiry);
        map.put(key, n);
        buckets.computeIfAbsent(1, f -> new FreqBucket()).addHead(n);
        if (expiry != 0) {
            expiryList.insertSorted(n);   // sorted insert by expiry time
        }
        minFreq = 1;   // new node always starts at freq=1 → reset minFreq
    }

    // Sweep expired entries — scan from front while expired, evict and advance.
    // Same pattern as removing a duplicate group from a sorted list: stop at the first
    // node that no longer matches the condition (expired). O(expired) not O(capacity).
    // Call from a background thread.
    public void sweepExpired(long currentTime) {
        while (true) {
            Node front = expiryList.peekFront();
            if (front == null || !front.isExpired(currentTime)) {
                break;
            }
            evict(front);   // evict removes from expiry list, freq bucket, and map
        }
    }

    // Partition pattern: promote re-routes a node from bucket[freq] to bucket[freq+1]
    // — exactly like moving a node from the "less" partition to the "greater" partition
    // while preserving relative order within the bucket.
    private void promote(Node n) {
        FreqBucket fb = buckets.get(n.freq);
        fb.remove(n);
        if (fb.isEmpty()) {
            buckets.remove(n.freq);
            if (n.freq == minFreq) {
                minFreq++;   // promote always goes to freq+1, so minFreq++ is exact here
            }
        }
        n.freq++;
        buckets.computeIfAbsent(n.freq, f -> new FreqBucket()).addHead(n);
    }

    // Evict victim by LFU-LRU, but prefer an already-expired entry first (O(1) check).
    // The sorted expiry list front is the soonest-to-expire — if it has already lapsed,
    // taking it avoids wasting a valid LFU slot.
    private void evictLFU(long currentTime) {
        Node soonest = expiryList.peekFront();
        if (soonest != null && soonest.isExpired(currentTime)) {
            evict(soonest);   // expired-first: free an already-dead slot, not a live one
            return;
        }
        FreqBucket fb = buckets.get(minFreq);
        if (fb == null || fb.isEmpty()) {
            return;
        }
        evict(fb.peekLRU());
    }

    // Single entry point for all eviction paths — removes from map, expiry list,
    // and freq bucket in one place so no path can leave partial state behind.
    private void evict(Node n) {
        if (n == null) {
            return;
        }
        map.remove(n.key);
        expiryList.remove(n);   // no-op if node has no TTL (ePrev/eNext already null)
        FreqBucket fb = buckets.get(n.freq);
        if (fb != null) {
            fb.remove(n);       // no-op if already removed (guard fires)
            if (fb.isEmpty()) {
                buckets.remove(n.freq);
                if (n.freq == minFreq) {
                    updateMinFreq();
                }
            }
        }
    }

    // Walk upward from minFreq to find the next non-empty bucket.
    // Needed after arbitrary eviction — promote() uses minFreq++ directly since it
    // always moves to minFreq+1 which it just populated.
    private void updateMinFreq() {
        if (map.isEmpty()) {
            minFreq = 0;
            return;
        }
        while (!buckets.containsKey(minFreq) || buckets.get(minFreq).isEmpty()) {
            minFreq++;
        }
    }
}

Complexity:

Design Tradeoff: This design is O(1) for LFU operations, but expiry insertion is O(n) since we maintain a sorted list. If we wanted strict bounds, we could use a min-heap for expiry, giving O(log n) insert, but we'd lose O(1) arbitrary removal and need lazy deletion or index tracking. So this is a tradeoff between simplicity and worst-case guarantees.

Real World: Every production cache layer uses LFU + TTL together: Redis ALLKEYS-LFU eviction tracks frequency sketches and every key has an optional TTL. CDN edge caches keep popular assets longer (LFU eviction) while respecting cache-control max-age headers (TTL). The dual-list design — one per frequency bucket, one sorted expiry list — is inspired by the same principles used in production libraries like Caffeine: separating eviction policy from expiry tracking.

Variations:

1. O(log n) insertSorted — replace the sorted expiry list with a TreeMap<Long, Deque<Node>> (expiry bucket map). put becomes O(log n) for tree insertion, but sweepExpired remains O(expired). Useful when TTLs cluster into tiers (1 min / 5 min / 1 hr) rather than arbitrary per-key values.
2. LRU with TTL — drop frequency tracking; keep one doubly linked list (MRU at head) plus the expiry list. get moves the node to the head; eviction removes the tail. This is a strict subset of the LFU design — remove the freq field and the buckets map.

Interview Disguises:

• "Design an in-memory session store for an auth service. Sessions expire after 30 minutes of inactivity, and under memory pressure the least-used sessions are evicted first." — LFU cache where each get acts as the activity ping; TTL resets on every access.
• "You are building a DNS resolver cache. Each DNS record has a TTL from the record itself. Under memory pressure, evict the record queried least often. Design the data structure." — LFU cache where TTL comes from the DNS record's TTL field; sweepExpired runs in a background thread between queries.

Thread Safety Discussion: This implementation is single-threaded. Expect a follow-up: "How would you make this thread-safe?"

Every LFU operation touches shared global state (freqMap, minFreq, expiry list) — this rules out per-key techniques.

Sweep thread: Call sweepExpired(currentTime) from a background ScheduledExecutorService. Wrap in try-catch — unchecked exceptions silently cancel future scheduleAtFixedRate runs.

Quick Reference Table

When to Use Each Pattern

Fast & Slow Pointers

• Detect whether a cycle exists and where it starts
• Find the middle node to split or compare halves
• Use the first-middle variant (fast.next != null && fast.next.next != null) when the first half must be equal or one node longer (Reorder List, Sort List)
• Use the second-middle variant (fast != null && fast.next != null) when you just need any middle (Palindrome, basic Middle)

In-Place Reversal

• Reverse the whole list or a subrange in O(1) space
• Use the front-insertion trick for partial reversal — avoids splitting and rejoining the list
• Always used as a helper step in multi-step problems (Palindrome, Reorder List)

Gap-Based Two Pointers

• Remove or locate a node exactly k positions from the end
• Find intersection of two lists by equalizing total path lengths with a head-swap
• Always start from a dummy node so the gap technique works even if the head is the target

Two-List Merge / Partition

• Merge two sorted lists in O(1) space using a dummy node
• Partition a list into two groups while preserving relative order — build two separate lists, then connect them
• Always null-terminate the second list before connecting — its tail pointer still points into the original list

Common Mistakes to Avoid

Fast & Slow Mistakes

1. Wrong loop condition — while (fast != null && fast.next != null) is required; checking only fast != null causes a NullPointerException on fast.next.next
2. Wrong middle variant — first-middle stops one step earlier (fast.next != null && fast.next.next != null); mixing the two variants in multi-step problems produces off-by-one bugs

Reversal Mistakes

3. Forgetting to save next before reversing — curr.next = prev destroys the reference to the rest of the list; always do ListNode next = curr.next first
4. Not null-terminating after split — after slow.next = null, the first half is correctly ended; skipping this creates a cycle through the second half

Gap & Dummy Node Mistakes

5. Gap of n instead of n+1 for deletion — advancing first by n only lands second on the target itself; you need second one node before it to set second.next = second.next.next
6. Skipping the dummy node — without a dummy, deleting the head requires a special case; dummy absorbs it automatically

Two-List Merge / Partition Mistakes

7. Forgetting greater.next = null — the greater tail still points into the original list; not null-terminating creates a cycle that causes infinite loops
8. Using <= x instead of < x in Partition — the problem requires < x for the less side; equal values go into the greater side

General Linked List Mistakes

9. Not checking head == null at the start — most operations on null head cause NullPointerException; add the guard at the top
10. Moving curr instead of saving and moving — in merge loops, always do curr = curr.next after setting curr.next; skipping this leaves curr pointing at a stale node