1. Reverse Linked List
Easy · LC 206
Given the head of a singly linked list, reverse it and return the new head. Walk the list with prev and cur pointers, saving cur.next into a temporary, pointing cur.next back at prev, then advancing both pointers one step. The order of operations is everything: capture next before rewiring or the rest of the list is lost, and prev ends as the new head when cur runs off the end.
def reverse_list(head: "ListNode | None") -> "ListNode | None":
"""LC 206. Reverse Linked List.
Walk the list with prev and cur pointers: save cur.next into a
temporary, point cur.next back at prev, then advance both one step.
Capturing next before rewiring is everything -- otherwise the rest
of the list is lost -- and prev is the new head when cur runs off
the end. O(n) time, O(1) space.
"""
prev = None
cur = head
while cur:
following = cur.next # capture before rewiring severs the walk
cur.next = prev
prev = cur
cur = following
return prev
// LC 206. Walk with prev/cur, saving cur->next before pointing it back at
// prev; prev is the new head once cur runs off the end.
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* after = cur->next; // capture before rewiring or the rest is lost
cur->next = prev;
prev = cur;
cur = after;
}
return prev;
}
/// LC 206. The three-pointer walk in ownership form: `take` the rest of
/// the list out of the current node (capturing next before rewiring),
/// point the node back at `prev`, and hand ownership over. When the input
/// runs dry, `prev` owns the whole reversed list.
pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut prev = None;
while let Some(mut node) = head {
head = node.next.take();
node.next = prev;
prev = Some(node);
}
prev
}
/** LC 206. Walk with prev/cur, saving cur.next before pointing it back; prev ends as the new head. */
export function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let cur = head;
while (cur !== null) {
const next = cur.next; // capture before rewiring or the rest of the list is lost
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
// LC 206. Walk with prev/cur, capturing cur.Next before pointing it back at
// prev; prev is the new head once cur runs off the end.
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
after := cur.Next // capture before rewiring or the rest is lost
cur.Next = prev
prev = cur
cur = after
}
return prev
}
// LC 206. Walk with prev/cur, saving cur.next before pointing it back at
// prev; prev is the new head once cur runs off the end.
func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var cur = head
while let node = cur {
let after = node.next // capture before rewiring or the rest is lost
node.next = prev
prev = node
cur = after
}
return prev
}
2. Merge Two Sorted Lists
Easy · LC 21
Given the heads of two sorted linked lists, splice them into one sorted list and return its head. Create a dummy node, keep a tail pointer, and repeatedly attach whichever list's current node is smaller, advancing that list, then attach the leftover remainder when one list empties. The dummy head removes every special case around an empty result or choosing the first node, and reusing the existing nodes keeps it O(1) extra space.
def merge_two_lists(
list1: "ListNode | None", list2: "ListNode | None"
// LC 21. Dummy head plus a tail pointer: repeatedly attach the smaller front
// node, then attach whichever list is left over. Reuses the existing nodes,
// so O(1) extra space, and the dummy removes every empty-result special case.
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 && list2) {
if (list1->val <= list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 ? list1 : list2; // splice in the remainder
return dummy.next;
}
/// LC 21. Dummy head plus a tail cursor: whichever list's head is smaller
/// gets detached and spliced onto the tail, and when one list empties the
/// other attaches whole. The dummy erases every empty-result special case,
/// and reusing the existing nodes keeps it O(1) extra space.
pub fn merge_two_lists(
mut list1: Option<Box<ListNode>>,
mut list2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(0));
let mut tail = &mut dummy;
while list1.is_some() && list2.is_some() {
let first_smaller = list1.as_ref().unwrap().val <= list2.as_ref().unwrap().val;
let source = if first_smaller { &mut list1 } else { &mut list2 };
let mut node = source.take().unwrap();
*source = node.next.take();
tail.next = Some(node);
tail = tail.next.as_mut().unwrap();
}
tail.next = list1.or(list2);
dummy.next
}
/** LC 21. Dummy head + tail pointer: attach the smaller current node, then splice on the remainder. */
export function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
const dummy = new ListNode();
let tail = dummy;
while (list1 !== null && list2 !== null) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = list1 ?? list2; // whichever list still has nodes is already sorted
return dummy.next;
}
// LC 21. Dummy head plus a tail pointer: repeatedly splice on whichever front
// node is smaller, then attach the surviving remainder. O(1) extra space.
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for list1 != nil && list2 != nil {
if list1.Val <= list2.Val {
tail.Next = list1
list1 = list1.Next
} else {
tail.Next = list2
list2 = list2.Next
}
tail = tail.Next
}
if list1 != nil { // splice in the remainder
tail.Next = list1
} else {
tail.Next = list2
}
return dummy.Next
}
// LC 21. Dummy head plus a tail pointer: repeatedly attach the smaller front
// node, then attach whichever list is left over. Reuses the existing nodes.
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
let dummy = ListNode()
var tail = dummy
var l1 = list1
var l2 = list2
while let a = l1, let b = l2 {
if a.val <= b.val {
tail.next = a
l1 = a.next
} else {
tail.next = b
l2 = b.next
}
tail = tail.next!
}
tail.next = l1 ?? l2 // the surviving remainder is already sorted
return dummy.next
}
3. Linked List Cycle
Easy · LC 141
Given the head of a linked list, return whether following next pointers ever revisits a node, meaning a cycle exists. March a slow pointer one step and a fast pointer two steps; if fast runs off the end the list is acyclic, and if the pointers meet there is a cycle. They must meet because inside a cycle fast gains one node on slow per step, so it can never jump over slow.
def has_cycle(head: "ListNode | None") -> bool:
"""LC 141. Linked List Cycle.
March a slow pointer one step and a fast pointer two: fast running
off the end proves the list is acyclic, and the pointers meeting
proves a cycle. They must meet because inside a cycle fast gains
exactly one node on slow per step, so it can never jump over slow.
O(n) time, O(1) space.
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
// LC 141. Floyd: slow steps once, fast twice. Fast hitting null means
// acyclic; inside a cycle fast gains one node per step, so it must meet slow.
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
/// LC 141. A cycle needs two owners of one node, which `Option<Box<...>>`
/// cannot express, so this uses the equivalent index representation:
/// `next_index[i]` is node i's successor and -1 is null, `start` the head.
/// Floyd is unchanged: fast moves two, slow moves one; fast either runs
/// off the end (acyclic) or, gaining one node per step, laps slow (cycle).
pub fn has_cycle(next_index: Vec<i32>, start: i32) -> bool {
let step = |i: i32| if i < 0 { -1 } else { next_index[i as usize] };
let mut slow = start;
let mut fast = start;
loop {
slow = step(slow);
fast = step(step(fast));
if fast < 0 {
return false;
}
if slow == fast {
return true;
}
}
}
/** LC 141. Slow moves one, fast moves two; inside a cycle fast gains one node per step, so they must meet. */
export function hasCycle(head: ListNode | null): boolean {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next; // slow trails fast, so it cannot be null while fast is in bounds
fast = fast.next.next;
if (slow === fast) return true;
}
return false; // fast ran off the end: acyclic
}
// LC 141. Floyd: slow steps once, fast twice. Fast hitting nil means acyclic;
// inside a cycle fast gains one node per step, so it must meet slow.
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
// LC 141. Floyd: slow steps once, fast twice. Fast hitting nil means acyclic;
// inside a cycle fast gains one node per step, so it must meet slow.
func hasCycle(_ head: ListNode?) -> Bool {
var slow = head
var fast = head
while let stepOne = fast?.next, let stepTwo = stepOne.next {
slow = slow!.next
fast = stepTwo
if slow === fast { return true }
}
return false
}
4. Reorder List
Medium · LC 143
Given a list L0, L1, ..., Ln, rearrange it in place into L0, Ln, L1, Ln-1, and so on, alternating front and back nodes. Find the middle with slow and fast pointers, reverse the second half, then interleave the two halves by alternating splices. Remember to cut the first half's tail to null before interleaving, and the front half may hold one extra node when the length is odd, so it leads the merge.
def reorder_list(head: "ListNode | None") -> None:
"""LC 143. Reorder List.
Rearrange L0, L1, ..., Ln into L0, Ln, L1, Ln-1, ... in place in
three phases: find the middle with slow and fast pointers, reverse
the second half, then interleave the halves by alternating splices.
The front half's tail must be cut to None before interleaving, and
on odd lengths the front holds one extra node, so it leads the
merge. O(n) time, O(1) space.
"""
slow = head
fast = head
while fast.next and fast.next.next: # slow stops on the front half's last node
slow = slow.next
fast = fast.next.next
back = slow.next
slow.next = None # cut the seam, or interleaving would build a cycle
prev = None
while back:
following = back.next
back.next = prev
prev = back
back = following
front = head
back = prev
while back: # front is never the shorter half, so back drives the loop
front_next = front.next
back_next = back.next
front.next = back
back.next = front_next
front = front_next
back = back_next
// LC 143. Find the middle with slow/fast, reverse the second half, then
// interleave. The first half is cut to null and may hold one extra node when
// the length is odd, so it leads the merge.
void reorderList(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* second = slow->next;
slow->next = nullptr; // cut the first half's tail before interleaving
ListNode* prev = nullptr;
while (second) {
ListNode* after = second->next;
second->next = prev;
prev = second;
second = after;
}
ListNode* first = head;
second = prev;
while (second) {
ListNode* firstAfter = first->next;
ListNode* secondAfter = second->next;
first->next = second;
second->next = firstAfter;
first = firstAfter;
second = secondAfter;
}
}
/// LC 143. Split at the middle (the front half keeps the extra node on odd
/// lengths), reverse the back half, then interleave with the front leading.
/// Taking the split point's next with `take` also cuts the first half's
/// tail to None -- the step pointer versions have to remember explicitly.
pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
let mut len = 0;
let mut cursor = head.as_ref();
while let Some(node) = cursor {
len += 1;
cursor = node.next.as_ref();
}
if len < 3 {
return;
}
// Walk to the last node of the front half: ceil(len / 2) nodes stay.
let mut split = head.as_mut().unwrap();
for _ in 1..(len + 1) / 2 {
split = split.next.as_mut().unwrap();
}
let mut back = reverse_list(split.next.take());
let mut front = head.as_mut();
while let Some(mut node) = back {
back = node.next.take();
let front_node = front.unwrap();
node.next = front_node.next.take();
front_node.next = Some(node);
// Skip past the node just spliced in to the next front position.
front = front_node.next.as_mut().unwrap().next.as_mut();
}
}
/** LC 143. Slow/fast find the middle, reverse the back half, then interleave with alternating splices. */
export function reorderList(head: ListNode | null): void {
if (head === null || head.next === null) return;
// fast starts a step ahead so slow stops at the front half's tail (front keeps the odd extra node)
let slow = head;
let fast: ListNode | null = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next!;
fast = fast.next.next;
}
let back = reverseList(slow.next);
slow.next = null; // cut the front half's tail before interleaving
let front: ListNode | null = head;
while (back !== null) {
const frontNext: ListNode | null = front!.next;
const backNext: ListNode | null = back.next;
front!.next = back;
back.next = frontNext;
front = frontNext;
back = backNext;
}
}
// LC 143. Find the middle with slow/fast, reverse the second half, then
// interleave; cutting the front half's tail first is what stops a cycle.
func reorderList(head *ListNode) {
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
second := slow.Next
slow.Next = nil // cut the first half's tail before interleaving
var prev *ListNode
for second != nil {
after := second.Next
second.Next = prev
prev = second
second = after
}
first := head
second = prev
for second != nil { // the front half is never shorter, so second drives
firstAfter := first.Next
secondAfter := second.Next
first.Next = second
second.Next = firstAfter
first = firstAfter
second = secondAfter
}
}
// LC 143. Find the middle with slow/fast, reverse the back half, then
// interleave. The front half's tail is cut to nil first, and on odd lengths
// the front holds one extra node, so it leads the merge.
func reorderList(_ head: ListNode?) {
guard let head = head else { return }
var slow = head
var fast = head
while let stepOne = fast.next, let stepTwo = stepOne.next {
slow = slow.next! // slow stops on the front half's last node
fast = stepTwo
}
var back = slow.next
slow.next = nil // cut the seam, or interleaving would build a cycle
var prev: ListNode? = nil
while let node = back {
let after = node.next
node.next = prev
prev = node
back = after
}
var front: ListNode? = head
back = prev
while let backNode = back { // front is never the shorter half, so back drives
let frontAfter = front!.next
let backAfter = backNode.next
front!.next = backNode
backNode.next = frontAfter
front = frontAfter
back = backAfter
}
}
5. Remove Nth Node From End of List
Medium · LC 19
Given a linked list head and an integer n, remove the nth node from the end in one pass and return the head. Start two pointers at a dummy before the head, advance the lead n steps, then walk both together until the lead hits the last node. The trail then sits just before the target, so one next reassignment removes it, and the dummy is what lets the head itself be deleted cleanly.
def remove_nth_from_end(head: "ListNode | None", n: int) -> "ListNode | None":
"""LC 19. Remove Nth Node From End of List.
Start lead and trail pointers at a dummy before the head, advance
the lead n steps, then walk both together until the lead reaches
the last node. The trail then sits just before the target, so one
next reassignment removes it, and the dummy is what lets the head
itself be deleted cleanly. One pass: O(n) time, O(1) space.
"""
dummy_head = ListNode(0, head)
lead = dummy_head
trail = dummy_head
for _ in range(n):
lead = lead.next
while lead.next:
lead = lead.next
trail = trail.next
trail.next = trail.next.next # trail sits just before the nth-from-end node
return dummy_head.next
// LC 19. One pass: lead starts n steps ahead of trail, both from a dummy;
// when lead hits the last node, trail sits just before the target. The dummy
// is what lets the head itself be deleted cleanly.
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode* lead = &dummy;
ListNode* trail = &dummy;
for (int i = 0; i < n; ++i) lead = lead->next;
while (lead->next) {
lead = lead->next;
trail = trail->next;
}
ListNode* doomed = trail->next;
trail->next = doomed->next;
delete doomed;
return dummy.next;
}
/// LC 19. Count the length, then walk a cursor from a dummy len - n steps
/// to the node just before the target and bypass it in one reassignment.
/// The dummy lets the head itself be deleted cleanly; counting is the
/// cleanest form under ownership (two live cursors fight the borrow checker).
pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
let mut len = 0;
let mut cursor = head.as_ref();
while let Some(node) = cursor {
len += 1;
cursor = node.next.as_ref();
}
let mut dummy = Box::new(ListNode { val: 0, next: head });
let mut before = &mut dummy;
for _ in 0..len - n {
before = before.next.as_mut().unwrap();
}
let target = before.next.take().unwrap();
before.next = target.next;
dummy.next
}
/** LC 19. From a dummy, send a lead pointer n ahead, then walk both; trail stops just before the target. */
export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let lead = dummy;
for (let step = 0; step < n; step++) lead = lead.next!;
let trail = dummy;
while (lead.next !== null) {
lead = lead.next;
trail = trail.next!;
}
trail.next = trail.next!.next; // one reassignment deletes the node; the dummy covers deleting the head
return dummy.next;
}
// LC 19. One pass: lead starts n steps ahead of trail, both from a dummy;
// when lead hits the last node, trail sits just before the target.
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
lead, trail := dummy, dummy
for i := 0; i < n; i++ {
lead = lead.Next
}
for lead.Next != nil {
lead = lead.Next
trail = trail.Next
}
trail.Next = trail.Next.Next // trail sits just before the nth-from-end node
return dummy.Next
}
// LC 19. One pass: lead starts n steps ahead of trail, both from a dummy;
// when lead hits the last node, trail sits just before the target. The dummy
// is what lets the head itself be deleted cleanly.
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
let dummy = ListNode(0, head)
var lead = dummy
var trail = dummy
for _ in 0..<n { lead = lead.next! }
while let after = lead.next {
lead = after
trail = trail.next!
}
trail.next = trail.next?.next // trail sits just before the nth-from-end node
return dummy.next
}
6. Copy List With Random Pointer
Medium · LC 138
Given a linked list whose nodes each have a next pointer and a random pointer to any node or null, return a deep copy. Do one pass building a hash map from each original node to a fresh clone, then a second pass wiring every clone's next and random through the map. The map resolves random pointers that target nodes not yet visited; the O(1) space variant interleaves each clone after its original instead.
def copy_random_list(head: "RandomNode | None") -> "RandomNode | None":
"""LC 138. Copy List With Random Pointer.
Two passes with a hash map from each original node to a fresh
clone: the first pass creates every clone, the second wires each
clone's next and random through the map. The map is what resolves
random pointers aimed at nodes not yet visited. O(n) time, O(n)
space.
"""
clone_of = {None: None} # mapping None lets null pointers copy with no branching
node = head
while node:
clone_of[node] = RandomNode(node.val)
node = node.next
node = head
while node:
clone_of[node].next = clone_of[node.next]
clone_of[node].random = clone_of[node.random]
node = node.next
return clone_of[head]
// LC 138. Two passes with a hash map from original node to fresh clone: the
// first pass allocates, the second wires next and random through the map,
// which resolves random pointers that target nodes not yet visited.
RandomNode* copyRandomList(RandomNode* head) {
unordered_map<RandomNode*, RandomNode*> cloneOf;
cloneOf[nullptr] = nullptr; // lets the wiring pass skip null checks
for (RandomNode* node = head; node; node = node->next)
cloneOf[node] = new RandomNode(node->val);
for (RandomNode* node = head; node; node = node->next) {
cloneOf[node]->next = cloneOf[node->next];
cloneOf[node]->random = cloneOf[node->random];
}
return cloneOf[head];
}
/// LC 138. A random pointer aliases a node that some `next` already owns,
/// which Box ownership forbids, so the equivalent representation is
/// (val, random_index) pairs with `next` implied by Vec order. The two
/// passes mirror the pointer version exactly: clone every node into an
/// old -> clone map, then wire each clone's random through the map (which
/// is what resolves randoms that point at nodes not yet visited).
pub fn copy_random_list(nodes: Vec<(i32, Option<usize>)>) -> Vec<(i32, Option<usize>)> {
let mut old_to_clone: HashMap<usize, usize> = HashMap::new();
let mut clones: Vec<(i32, Option<usize>)> = Vec::with_capacity(nodes.len());
for (i, &(val, _)) in nodes.iter().enumerate() {
old_to_clone.insert(i, clones.len());
clones.push((val, None));
}
for (i, &(_, random)) in nodes.iter().enumerate() {
clones[old_to_clone[&i]].1 = random.map(|r| old_to_clone[&r]);
}
clones
}
/** LC 138. Pass one maps each original to a fresh clone; pass two wires next/random through the map. */
export function copyRandomList(head: RandomNode | null): RandomNode | null {
if (head === null) return null;
const cloneOf = new Map<RandomNode, RandomNode>();
for (let node: RandomNode | null = head; node !== null; node = node.next) {
cloneOf.set(node, new RandomNode(node.val));
}
for (let node: RandomNode | null = head; node !== null; node = node.next) {
const clone = cloneOf.get(node)!;
clone.next = node.next === null ? null : cloneOf.get(node.next)!;
// the map resolves random pointers even when they target nodes later in the list
clone.random = node.random === null ? null : cloneOf.get(node.random)!;
}
return cloneOf.get(head)!;
}
// LC 138. Two passes with a map from original node to fresh clone: the first
// pass allocates, the second wires Next and Random through the map.
func copyRandomList(head *Node) *Node {
cloneOf := map[*Node]*Node{nil: nil} // mapping nil lets nil pointers copy with no branching
for node := head; node != nil; node = node.Next {
cloneOf[node] = &Node{Val: node.Val}
}
for node := head; node != nil; node = node.Next {
cloneOf[node].Next = cloneOf[node.Next]
cloneOf[node].Random = cloneOf[node.Random]
}
return cloneOf[head]
}
// LC 138. Two passes with a map from each original node to a fresh clone: the
// first pass allocates, the second wires next and random through the map,
// which resolves random pointers aimed at nodes not yet visited.
func copyRandomList(_ head: Node?) -> Node? {
var cloneOf: [ObjectIdentifier: Node] = [:]
var node = head
while let original = node {
cloneOf[ObjectIdentifier(original)] = Node(original.val)
node = original.next
}
node = head
while let original = node {
let clone = cloneOf[ObjectIdentifier(original)]!
clone.next = original.next.flatMap { cloneOf[ObjectIdentifier($0)] }
clone.random = original.random.flatMap { cloneOf[ObjectIdentifier($0)] }
node = original.next
}
return head.flatMap { cloneOf[ObjectIdentifier($0)] }
}
7. Add Two Numbers
Medium · LC 2
Given two non-empty linked lists storing non-negative integers in reverse digit order, return their sum as a list in the same format. Walk both lists in step, adding the two current digits plus the carry, appending sum mod 10 to a dummy-headed result and carrying sum / 10 forward. Loop while either list has nodes or the carry is nonzero; forgetting the final carry drops the leading digit on sums like 5 plus 5.
def add_two_numbers(
l1: "ListNode | None", l2: "ListNode | None"
// LC 2. Walk both lists in step adding digits plus the carry, appending
// sum % 10 to a dummy-headed result. Looping while the carry is nonzero is
// what keeps the leading digit on sums like 5 + 5.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = carry;
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
tail->next = new ListNode(sum % 10);
tail = tail->next;
carry = sum / 10;
}
return dummy.next;
}
/// LC 2. Digits arrive in reverse order, so walk both lists in step,
/// appending (digit sum + carry) % 10 behind a dummy and carrying / 10
/// forward. Looping while a carry remains is what keeps 5 + 5 = [0, 1].
pub fn add_two_numbers(
mut l1: Option<Box<ListNode>>,
mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(0));
let mut tail = &mut dummy;
let mut carry = 0;
while l1.is_some() || l2.is_some() || carry > 0 {
let mut sum = carry;
if let Some(node) = l1 {
sum += node.val;
l1 = node.next;
}
if let Some(node) = l2 {
sum += node.val;
l2 = node.next;
}
carry = sum / 10;
tail.next = Some(Box::new(ListNode::new(sum % 10)));
tail = tail.next.as_mut().unwrap();
}
dummy.next
}
/** LC 2. Dummy-headed sum list: digit + digit + carry, append sum % 10, loop while nodes or carry remain. */
export function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode();
let tail = dummy;
let carry = 0;
while (l1 !== null || l2 !== null || carry > 0) {
// looping on carry > 0 keeps the leading digit on sums like 5 + 5
const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
carry = Math.floor(sum / 10);
tail.next = new ListNode(sum % 10);
tail = tail.next;
l1 = l1?.next ?? null;
l2 = l2?.next ?? null;
}
return dummy.next;
}
// LC 2. Grade-school addition over the reversed digit lists; looping while
// the carry survives keeps the leading digit on sums like 5 + 5.
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
carry := 0
for l1 != nil || l2 != nil || carry != 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
tail.Next = &ListNode{Val: sum % 10}
tail = tail.Next
carry = sum / 10
}
return dummy.Next
}
// LC 2. Grade-school addition over the reversed digit lists: append
// sum % 10 behind a dummy head and ride sum / 10 forward. Looping while the
// carry survives is what keeps the leading digit on sums like 5 + 5.
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode()
var tail = dummy
var a = l1
var b = l2
var carry = 0
while a != nil || b != nil || carry != 0 {
let sum = (a?.val ?? 0) + (b?.val ?? 0) + carry
carry = sum / 10
tail.next = ListNode(sum % 10)
tail = tail.next!
a = a?.next
b = b?.next
}
return dummy.next
}
8. Find The Duplicate Number
Medium · LC 287
Given n+1 integers in the range 1 to n with one repeated value, find the duplicate without modifying the array, in O(1) space. Treat index i as a node pointing to nums[i] and run Floyd's algorithm: after fast and slow meet, restart one pointer at zero and advance both in single steps. They reconverge at the cycle entrance, which is the duplicate, since two indices holding the same value point at the same node.
def find_duplicate(nums: list[int]) -> int:
"""LC 287. Find the Duplicate Number.
Treat index i as a node whose next pointer is nums[i]; the repeated
value means two indices point at the same node, forming a cycle
whose entrance is the duplicate. Run Floyd's algorithm: after slow
and fast meet, restart one pointer at zero and advance both in
single steps until they reconverge at the entrance. O(n) time,
O(1) space, array untouched.
"""
slow = 0
fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
finder = 0 # index 0 is outside the cycle: values 1..n never point back to it
while finder != slow:
finder = nums[finder]
slow = nums[slow]
return finder
// LC 287. Treat index i as a node pointing at nums[i]; two indices holding
// the same value point at the same node, so the duplicate is a cycle
// entrance. Floyd: after slow and fast meet, restart one pointer at zero and
// step both singly until they reconverge. O(1) space, array untouched.
int findDuplicate(vector<int> nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
int finder = 0;
while (finder != slow) { // both are now cycle-entrance steps from the entrance
finder = nums[finder];
slow = nums[slow];
}
return finder;
}
/// LC 287. Read index i as a list node whose successor is nums[i]; the
/// duplicate value gives one node two in-edges, i.e. a cycle entrance.
/// Floyd phase one meets inside the cycle; phase two restarts one pointer
/// at index 0 and single-steps both until they reconverge at the entrance,
/// all without modifying the array and in O(1) space.
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let mut slow = nums[0] as usize;
let mut fast = nums[nums[0] as usize] as usize;
while slow != fast {
slow = nums[slow] as usize;
fast = nums[nums[fast] as usize] as usize;
}
let mut finder = 0;
while finder != slow {
finder = nums[finder] as usize;
slow = nums[slow] as usize;
}
slow as i32
}
/** LC 287. Treat index i as a node pointing at nums[i]; after Floyd's meeting, restart one pointer at 0. */
export function findDuplicate(nums: number[]): number {
let slow = 0;
let fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
// single-stepping from 0 and from the meeting point reconverges at the cycle entrance: the duplicate
let finder = 0;
while (finder !== slow) {
finder = nums[finder];
slow = nums[slow];
}
return finder;
}
// LC 287. Treat index i as a node pointing at nums[i]; the duplicate is a
// cycle entrance, found by Floyd's meet-then-restart walk. Array untouched.
func findDuplicate(nums []int) int {
slow, fast := 0, 0
for {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
finder := 0 // index 0 is outside the cycle: values 1..n never point back to it
for finder != slow {
finder = nums[finder]
slow = nums[slow]
}
return finder
}
// LC 287. The array is a linked list in disguise: index i points at nums[i],
// so the duplicate is a cycle entrance. Floyd: after slow and fast meet,
// restart one pointer at zero and step both singly until they reconverge.
func findDuplicate(_ nums: [Int]) -> Int {
var slow = 0
var fast = 0
repeat {
slow = nums[slow]
fast = nums[nums[fast]]
} while slow != fast
var finder = 0 // index 0 is outside the cycle: values 1..n never point at it
while finder != slow {
finder = nums[finder]
slow = nums[slow]
}
return finder
}
9. Reverse Linked List II
Medium · LC 92
Given a list and positions left and right, reverse the sublist between those positions in one pass and return the head. From a dummy node, walk to the node before position left, then do right minus left head insertions, each detaching the node after the sublist start and relinking it after the anchor. The anchor and original sublist head stay fixed, keeping both seams connected, and the dummy covers reversal starting at the head.
def reverse_between(
head: "ListNode | None", left: int, right: int
// LC 92. Walk a dummy-rooted anchor to just before position left, then do
// right - left head insertions: each detaches the node after the sublist
// start and relinks it right after the anchor. Anchor and sublist start stay
// fixed, keeping both seams connected.
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0);
dummy.next = head;
ListNode* anchor = &dummy;
for (int i = 1; i < left; ++i) anchor = anchor->next;
ListNode* sublistStart = anchor->next; // stays put; ends as the sublist tail
for (int i = 0; i < right - left; ++i) {
ListNode* moving = sublistStart->next;
sublistStart->next = moving->next;
moving->next = anchor->next;
anchor->next = moving;
}
return dummy.next;
}
/// LC 92. Walk an anchor from a dummy to the node before `left` (the
/// dummy covers reversal starting at the head), detach everything after
/// it, reverse exactly right - left + 1 nodes with the take/relink walk,
/// and splice the block back. The block's original first node surfaces as
/// its tail, so walking the anchor onto it reattaches the remainder and
/// keeps both seams connected.
pub fn reverse_between(
head: Option<Box<ListNode>>,
left: i32,
right: i32,
) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode { val: 0, next: head });
let mut anchor = &mut dummy;
for _ in 1..left {
anchor = anchor.next.as_mut().unwrap();
}
let mut rest = anchor.next.take();
let mut reversed = None;
for _ in 0..=right - left {
let mut node = rest.unwrap();
rest = node.next.take();
node.next = reversed;
reversed = Some(node);
}
anchor.next = reversed;
// The block's original first node is now its tail: walk onto it.
for _ in 0..=right - left {
anchor = anchor.next.as_mut().unwrap();
}
anchor.next = rest;
dummy.next
}
/** LC 92. Walk a dummy to just before `left`, then do right - left head insertions after that anchor. */
export function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
const dummy = new ListNode(0, head);
let anchor = dummy; // stays fixed just before the sublist, keeping the left seam connected
for (let pos = 1; pos < left; pos++) anchor = anchor.next!;
const sublistTail = anchor.next!; // the original sublist head sinks to the sublist tail
for (let insertions = 0; insertions < right - left; insertions++) {
const lifted = sublistTail.next!;
sublistTail.next = lifted.next; // detaching here keeps the right seam connected
lifted.next = anchor.next;
anchor.next = lifted;
}
return dummy.next;
}
// LC 92. Walk an anchor to just before position left, then do right-left head
// insertions; the anchor and the sublist's first node never move, which keeps
// both seams connected.
func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummy := &ListNode{Next: head}
anchor := dummy
for i := 1; i < left; i++ {
anchor = anchor.Next
}
sublistStart := anchor.Next // stays put; ends as the sublist tail
for i := 0; i < right-left; i++ {
moving := sublistStart.Next
sublistStart.Next = moving.Next
moving.Next = anchor.Next // head-insert: moving lands right after the anchor
anchor.Next = moving
}
return dummy.Next
}
// LC 92. Walk a dummy-rooted anchor to just before position left, then do
// right - left head insertions: each detaches the node after the sublist
// start and relinks it right after the anchor. Anchor and sublist start stay
// fixed, keeping both seams connected.
func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
let dummy = ListNode(0, head)
var anchor = dummy
for _ in 1..<left { anchor = anchor.next! }
let sublistTail = anchor.next! // the original first node sinks to the sublist's tail
for _ in 0..<(right - left) {
let lifted = sublistTail.next!
sublistTail.next = lifted.next
lifted.next = anchor.next // head-insert: lifted lands right after the anchor
anchor.next = lifted
}
return dummy.next
}
10. Design Circular Queue
Medium · LC 622
Design a fixed-capacity circular queue supporting enQueue, deQueue, Front, Rear, isEmpty, and isFull. Back it with an array of size k plus a head index and a count; enqueue writes at (head + count) mod k, dequeue advances head modulo k, and the count answers isEmpty and isFull. Tracking the count is the trick, since it distinguishes a full buffer from an empty one when head and tail coincide.
class MyCircularQueue:
"""LC 622. Design Circular Queue.
Ring buffer: a fixed array of size k plus a head index and a live
count. Enqueue writes at (head + count) mod k, dequeue advances
head mod k, and tracking the count is the trick -- it distinguishes
a full buffer from an empty one when head and tail coincide. All
operations O(1), O(k) space.
"""
def __init__(self, k: int) -> None:
self._ring = [0] * k
self._head = 0
self._count = 0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self._ring[(self._head + self._count) % len(self._ring)] = value
self._count += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self._head = (self._head + 1) % len(self._ring)
self._count -= 1
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self._ring[self._head]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self._ring[(self._head + self._count - 1) % len(self._ring)]
def isEmpty(self) -> bool:
return self._count == 0
def isFull(self) -> bool:
return self._count == len(self._ring)
// LC 622. Fixed array plus a head index and a count; enqueue writes at
// (head + count) % k, dequeue advances head modulo k. The count is the trick:
// it tells a full buffer from an empty one when head and tail coincide.
class MyCircularQueue {
vector<int> ring;
int head = 0, count = 0;
public:
MyCircularQueue(int k) : ring(k) {}
bool enQueue(int value) {
if (isFull()) return false;
ring[(head + count) % ring.size()] = value;
++count;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
head = (head + 1) % static_cast<int>(ring.size());
--count;
return true;
}
int Front() { return isEmpty() ? -1 : ring[head]; }
int Rear() { return isEmpty() ? -1 : ring[(head + count - 1) % ring.size()]; }
bool isEmpty() { return count == 0; }
bool isFull() { return count == static_cast<int>(ring.size()); }
};
/// LC 622. Fixed Vec of size k plus a head index and a live count: enqueue
/// writes at (head + count) % k, dequeue advances head % k. Storing the
/// count instead of a tail index is the trick -- it cleanly separates full
/// from empty, the two states where head and tail coincide.
pub struct MyCircularQueue {
buffer: Vec<i32>,
head: usize,
count: usize,
}
impl MyCircularQueue {
pub fn new(k: i32) -> Self {
MyCircularQueue { buffer: vec![0; k as usize], head: 0, count: 0 }
}
pub fn en_queue(&mut self, value: i32) -> bool {
if self.is_full() {
return false;
}
let tail = (self.head + self.count) % self.buffer.len();
self.buffer[tail] = value;
self.count += 1;
true
}
pub fn de_queue(&mut self) -> bool {
if self.is_empty() {
return false;
}
self.head = (self.head + 1) % self.buffer.len();
self.count -= 1;
true
}
pub fn front(&self) -> i32 {
if self.is_empty() { -1 } else { self.buffer[self.head] }
}
pub fn rear(&self) -> i32 {
if self.is_empty() {
-1
} else {
self.buffer[(self.head + self.count - 1) % self.buffer.len()]
}
}
pub fn is_empty(&self) -> bool {
self.count == 0
}
pub fn is_full(&self) -> bool {
self.count == self.buffer.len()
}
}
/** LC 622. Fixed array + head index + count; the count is what tells a full ring from an empty one. */
export class MyCircularQueue {
private ring: number[];
private head = 0;
private count = 0;
constructor(k: number) {
this.ring = new Array<number>(k).fill(0);
}
enQueue(value: number): boolean {
if (this.isFull()) return false;
this.ring[(this.head + this.count) % this.ring.length] = value;
this.count++;
return true;
}
deQueue(): boolean {
if (this.isEmpty()) return false;
this.head = (this.head + 1) % this.ring.length;
this.count--;
return true;
}
Front(): number {
return this.isEmpty() ? -1 : this.ring[this.head];
}
Rear(): number {
return this.isEmpty() ? -1 : this.ring[(this.head + this.count - 1) % this.ring.length];
}
isEmpty(): boolean {
return this.count === 0;
}
isFull(): boolean {
return this.count === this.ring.length;
}
}
// MyCircularQueue is LC 622: a fixed ring plus a head index and a live count;
// the count is the trick -- it tells a full buffer from an empty one when
// head and tail coincide. All operations O(1).
type MyCircularQueue struct {
ring []int
head int
count int
}
func newMyCircularQueue(k int) *MyCircularQueue {
return &MyCircularQueue{ring: make([]int, k)}
}
func (q *MyCircularQueue) enQueue(value int) bool {
if q.isFull() {
return false
}
q.ring[(q.head+q.count)%len(q.ring)] = value
q.count++
return true
}
func (q *MyCircularQueue) deQueue() bool {
if q.isEmpty() {
return false
}
q.head = (q.head + 1) % len(q.ring)
q.count--
return true
}
func (q *MyCircularQueue) Front() int {
if q.isEmpty() {
return -1
}
return q.ring[q.head]
}
func (q *MyCircularQueue) Rear() int {
if q.isEmpty() {
return -1
}
return q.ring[(q.head+q.count-1)%len(q.ring)]
}
func (q *MyCircularQueue) isEmpty() bool { return q.count == 0 }
func (q *MyCircularQueue) isFull() bool { return q.count == len(q.ring) }
// LC 622. Fixed array plus a head index and a count; enqueue writes at
// (head + count) % k, dequeue advances head modulo k. The count is the trick:
// it tells a full buffer from an empty one when head and tail coincide.
class MyCircularQueue {
var ring: [Int]
var head = 0
var count = 0
init(_ k: Int) { ring = Array(repeating: 0, count: k) }
func enQueue(_ value: Int) -> Bool {
if isFull() { return false }
ring[(head + count) % ring.count] = value
count += 1
return true
}
func deQueue() -> Bool {
if isEmpty() { return false }
head = (head + 1) % ring.count
count -= 1
return true
}
func Front() -> Int { return isEmpty() ? -1 : ring[head] }
func Rear() -> Int { return isEmpty() ? -1 : ring[(head + count - 1) % ring.count] }
func isEmpty() -> Bool { return count == 0 }
func isFull() -> Bool { return count == ring.count }
}
11. LRU Cache
Medium · LC 146
Design a fixed-capacity cache where get and put both run in O(1) and put evicts the least recently used key when full. Pair a hash map from key to node with a doubly linked list ordered by recency; each access moves its node to the front, and eviction removes the node before the tail. Dummy head and tail sentinels eliminate null checks, and updating an existing key must still refresh its recency.
class LRUCache:
"""LC 146. LRU Cache.
A hash map from key to node paired with a doubly linked list
ordered most recent first: every get and put moves the touched node
to the front, and eviction unlinks the node just before the back
sentinel. Dummy front and back sentinels eliminate every null
check, and updating an existing key still refreshes its recency.
O(1) per operation, O(capacity) space.
"""
class _Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key: int, val: int) -> None:
self.key = key
self.val = val
self.prev: "LRUCache._Node | None" = None
self.next: "LRUCache._Node | None" = None
def __init__(self, capacity: int) -> None:
self._capacity = capacity
self._node_of: dict = {}
self._front = self._Node(0, 0) # sentinel on the most recent side
self._back = self._Node(0, 0) # sentinel on the least recent side
self._front.next = self._back
self._back.prev = self._front
def _unlink(self, node: "LRUCache._Node") -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _link_front(self, node: "LRUCache._Node") -> None:
node.prev = self._front
node.next = self._front.next
self._front.next.prev = node
self._front.next = node
def get(self, key: int) -> int:
if key not in self._node_of:
return -1
node = self._node_of[key]
self._unlink(node)
self._link_front(node) # a read refreshes recency too
return node.val
def put(self, key: int, value: int) -> None:
if key in self._node_of:
self._unlink(self._node_of.pop(key)) # an update must refresh recency
node = self._Node(key, value)
self._node_of[key] = node
self._link_front(node)
if len(self._node_of) > self._capacity:
stale = self._back.prev # least recently used sits before the back sentinel
self._unlink(stale)
del self._node_of[stale.key]
// LC 146. Hash map from key to a node in a std::list ordered by recency
// (front = most recent). Every access splices its node to the front; splice
// relinks in place and keeps iterators valid, so the map never goes stale.
// Eviction pops the back. All operations O(1).
class LRUCache {
int capacity;
list<pair<int, int>> recency; // (key, value), most recent at the front
unordered_map<int, list<pair<int, int>>::iterator> whereIs;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto found = whereIs.find(key);
if (found == whereIs.end()) return -1;
recency.splice(recency.begin(), recency, found->second); // iterator stays valid
return found->second->second;
}
void put(int key, int value) {
auto found = whereIs.find(key);
if (found != whereIs.end()) {
found->second->second = value;
recency.splice(recency.begin(), recency, found->second); // refresh recency too
return;
}
if (static_cast<int>(recency.size()) == capacity) {
whereIs.erase(recency.back().first); // least recently used lives at the back
recency.pop_back();
}
recency.push_front({key, value});
whereIs[key] = recency.begin();
}
};
/// LC 146. HashMap from key to slot plus a recency-ordered doubly linked
/// list living in a Vec arena: nodes refer to each other by index, so
/// relinking is plain usize writes and the borrow checker never sees a
/// shared pointer -- the classic Rust answer to intrusive lists. Slots 0
/// and 1 are head and tail sentinels (no null checks); every access
/// splices its node behind the head, and eviction recycles the slot just
/// before the tail. get and put are both O(1).
pub struct LRUCache {
capacity: usize,
slots: HashMap<i32, usize>,
arena: Vec<LruEntry>,
}
impl LRUCache {
pub fn new(capacity: i32) -> Self {
let arena = vec![
LruEntry { key: 0, value: 0, prev: 0, next: 1 }, // head sentinel
LruEntry { key: 0, value: 0, prev: 0, next: 1 }, // tail sentinel
];
LRUCache { capacity: capacity as usize, slots: HashMap::new(), arena }
}
fn detach(&mut self, slot: usize) {
let (prev, next) = (self.arena[slot].prev, self.arena[slot].next);
self.arena[prev].next = next;
self.arena[next].prev = prev;
}
fn attach_front(&mut self, slot: usize) {
let first = self.arena[0].next;
self.arena[slot].prev = 0;
self.arena[slot].next = first;
self.arena[first].prev = slot;
self.arena[0].next = slot;
}
pub fn get(&mut self, key: i32) -> i32 {
match self.slots.get(&key).copied() {
Some(slot) => {
self.detach(slot);
self.attach_front(slot);
self.arena[slot].value
}
None => -1,
}
}
pub fn put(&mut self, key: i32, value: i32) {
if let Some(slot) = self.slots.get(&key).copied() {
self.arena[slot].value = value;
// Updating an existing key must still refresh its recency.
self.detach(slot);
self.attach_front(slot);
return;
}
let slot = if self.slots.len() == self.capacity {
let lru = self.arena[1].prev; // least recent sits before the tail sentinel
self.detach(lru);
self.slots.remove(&self.arena[lru].key);
lru
} else {
self.arena.push(LruEntry { key: 0, value: 0, prev: 0, next: 0 });
self.arena.len() - 1
};
self.arena[slot].key = key;
self.arena[slot].value = value;
self.slots.insert(key, slot);
self.attach_front(slot);
}
}
/** LC 146. Map key -> node + a real doubly linked recency list; every access re-fronts its node, O(1) ops. */
export class LRUCache {
private nodeOf = new Map<number, CacheNode>();
private recency = new RecencyList();
private capacity: number;
constructor(capacity: number) {
this.capacity = capacity;
}
get(key: number): number {
const node = this.nodeOf.get(key);
if (node === undefined) return -1;
this.recency.remove(node); // re-fronting on every access is what makes the back least recently used
this.recency.addFirst(node);
return node.value;
}
put(key: number, value: number): void {
const existing = this.nodeOf.get(key);
if (existing !== undefined) {
existing.value = value;
this.recency.remove(existing); // updating an existing key still refreshes its recency
this.recency.addFirst(existing);
return;
}
if (this.nodeOf.size === this.capacity) {
this.nodeOf.delete(this.recency.popLast().key);
}
const node = new CacheNode(key, value);
this.nodeOf.set(key, node);
this.recency.addFirst(node);
}
}
// lruNode is LRUCache's doubly linked node; sentinels bracket the recency list.
type lruNode struct {
key, val int
prev, next *lruNode
}
// LRUCache is LC 146: a hash map from key to node in a doubly linked recency
// list, most recent at the front. Every get and put moves the touched node to
// the front; eviction unlinks the node before the back sentinel. O(1) per op.
type LRUCache struct {
capacity int
nodeOf map[int]*lruNode
front, back *lruNode // sentinels on the most and least recent sides
}
func newLRUCache(capacity int) *LRUCache {
front := &lruNode{}
back := &lruNode{}
front.next = back
back.prev = front
return &LRUCache{capacity: capacity, nodeOf: map[int]*lruNode{}, front: front, back: back}
}
func (c *LRUCache) unlink(node *lruNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (c *LRUCache) linkFront(node *lruNode) {
node.prev = c.front
node.next = c.front.next
c.front.next.prev = node
c.front.next = node
}
func (c *LRUCache) get(key int) int {
node, ok := c.nodeOf[key]
if !ok {
return -1
}
c.unlink(node)
c.linkFront(node) // a read refreshes recency too
return node.val
}
func (c *LRUCache) put(key int, value int) {
if node, ok := c.nodeOf[key]; ok {
c.unlink(node) // an update must refresh recency
delete(c.nodeOf, key)
}
node := &lruNode{key: key, val: value}
c.nodeOf[key] = node
c.linkFront(node)
if len(c.nodeOf) > c.capacity {
stale := c.back.prev // least recently used sits before the back sentinel
c.unlink(stale)
delete(c.nodeOf, stale.key)
}
}
// LC 146. Hash map from key to a node in a doubly linked list ordered most
// recent first; every get and put relinks the touched node at the front, and
// eviction unlinks the node before the back sentinel. The sentinels remove
// every nil check. All operations O(1).
class LRUCache {
class DListNode {
var key: Int
var val: Int
var prev: DListNode?
var next: DListNode?
init(_ key: Int, _ val: Int) { self.key = key; self.val = val }
}
let capacity: Int
var nodeOf: [Int: DListNode] = [:]
let front = DListNode(0, 0) // sentinel on the most recent side
let back = DListNode(0, 0) // sentinel on the least recent side
init(_ capacity: Int) {
self.capacity = capacity
front.next = back
back.prev = front
}
func unlink(_ node: DListNode) {
node.prev!.next = node.next
node.next!.prev = node.prev
}
func linkFront(_ node: DListNode) {
node.prev = front
node.next = front.next
front.next!.prev = node
front.next = node
}
func get(_ key: Int) -> Int {
guard let node = nodeOf[key] else { return -1 }
unlink(node)
linkFront(node) // a read refreshes recency too
return node.val
}
func put(_ key: Int, _ value: Int) {
if let existing = nodeOf.removeValue(forKey: key) {
unlink(existing) // an update must refresh recency
}
let node = DListNode(key, value)
nodeOf[key] = node
linkFront(node)
if nodeOf.count > capacity {
let stale = back.prev! // least recently used sits before the back sentinel
unlink(stale)
nodeOf[stale.key] = nil
}
}
}
12. LFU Cache
Hard · LC 460
Design a fixed-capacity cache with O(1) get and put where eviction removes the least frequently used key, breaking ties by least recent use. Keep a key-to-node map plus one doubly linked list per frequency bucket, and track the minimum frequency; each access moves a node into the next bucket. The minFreq pointer is the subtlety: it resets to 1 on every insertion and only increments when an access empties the bucket it points at.
class LFUCache:
"""LC 460. LFU Cache.
A key-to-(value, freq) map plus one OrderedDict per frequency
bucket, each ordered least recent first, and a min_freq pointer for
O(1) eviction. Every access moves its key into the next bucket; the
min_freq pointer is the subtlety -- it resets to 1 on every
insertion and only increments when an access drains the bucket it
points at. O(1) per operation, O(capacity) space.
"""
def __init__(self, capacity: int) -> None:
self._capacity = capacity
self._entry_of: dict = {} # key -> (value, freq)
self._buckets: dict = {} # freq -> OrderedDict of keys, least recent first
self._min_freq = 0
def _bump(self, key: int) -> None:
value, freq = self._entry_of[key]
del self._buckets[freq][key]
if not self._buckets[freq]:
del self._buckets[freq]
if self._min_freq == freq: # the bumped key lands in freq + 1, so this stays valid
self._min_freq = freq + 1
self._entry_of[key] = (value, freq + 1)
self._buckets.setdefault(freq + 1, OrderedDict())[key] = None
def get(self, key: int) -> int:
if key not in self._entry_of:
return -1
self._bump(key)
return self._entry_of[key][0]
def put(self, key: int, value: int) -> None:
if self._capacity <= 0:
return
if key in self._entry_of:
self._bump(key)
self._entry_of[key] = (value, self._entry_of[key][1])
return
if len(self._entry_of) == self._capacity:
# least recent key in the minimum-frequency bucket goes first
stale_key, _ = self._buckets[self._min_freq].popitem(last=False)
if not self._buckets[self._min_freq]:
del self._buckets[self._min_freq]
del self._entry_of[stale_key]
self._entry_of[key] = (value, 1)
self._buckets.setdefault(1, OrderedDict())[key] = None
self._min_freq = 1 # a brand-new key is always the least frequent
// LC 460. One recency-ordered std::list per frequency bucket plus a map from
// key to its node, and a minFreq pointer. Each access moves a node to the
// front of the next bucket. minFreq resets to 1 on every insertion and only
// increments when an access empties the bucket it points at.
class LFUCache {
struct Entry {
int key, value, freq;
};
int capacity, minFreq = 0;
unordered_map<int, list<Entry>> bucketOf; // freq -> entries, most recent at the front
unordered_map<int, list<Entry>::iterator> whereIs;
void bumpFrequency(list<Entry>::iterator node) {
int freq = node->freq;
bucketOf[freq + 1].push_front({node->key, node->value, freq + 1});
whereIs[node->key] = bucketOf[freq + 1].begin();
bucketOf[freq].erase(node);
if (bucketOf[freq].empty()) {
bucketOf.erase(freq);
if (minFreq == freq) ++minFreq; // only the emptied minimum bucket bumps it
}
}
public:
LFUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto found = whereIs.find(key);
if (found == whereIs.end()) return -1;
int value = found->second->value;
bumpFrequency(found->second);
return value;
}
void put(int key, int value) {
if (capacity == 0) return;
auto found = whereIs.find(key);
if (found != whereIs.end()) {
found->second->value = value;
bumpFrequency(found->second);
return;
}
if (static_cast<int>(whereIs.size()) == capacity) {
list<Entry>& lowestBucket = bucketOf[minFreq];
whereIs.erase(lowestBucket.back().key); // least recent within the lowest frequency
lowestBucket.pop_back();
if (lowestBucket.empty()) bucketOf.erase(minFreq);
}
bucketOf[1].push_front({key, value, 1});
whereIs[key] = bucketOf[1].begin();
minFreq = 1; // a fresh key always holds the minimum frequency
}
};
/// LC 460. entries maps key -> (value, freq) and buckets maps freq -> keys
/// ordered oldest-use-first, so eviction pops the front of the min_freq
/// bucket: least frequent, ties broken by least recently used. The
/// min_freq pointer is the subtlety: it resets to 1 on every insertion and
/// only climbs when an access drains the bucket it points at.
pub struct LFUCache {
capacity: usize,
min_freq: i32,
entries: HashMap<i32, (i32, i32)>,
buckets: HashMap<i32, Vec<i32>>,
}
impl LFUCache {
pub fn new(capacity: i32) -> Self {
LFUCache {
capacity: capacity as usize,
min_freq: 0,
entries: HashMap::new(),
buckets: HashMap::new(),
}
}
fn touch(&mut self, key: i32) {
let freq = self.entries.get(&key).unwrap().1;
let bucket = self.buckets.get_mut(&freq).unwrap();
let pos = bucket.iter().position(|&k| k == key).unwrap();
bucket.remove(pos);
if bucket.is_empty() {
self.buckets.remove(&freq);
if self.min_freq == freq {
self.min_freq = freq + 1; // this key was the only minimum-frequency key
}
}
self.entries.get_mut(&key).unwrap().1 = freq + 1;
self.buckets.entry(freq + 1).or_insert_with(Vec::new).push(key);
}
pub fn get(&mut self, key: i32) -> i32 {
if !self.entries.contains_key(&key) {
return -1;
}
self.touch(key);
self.entries[&key].0
}
pub fn put(&mut self, key: i32, value: i32) {
if self.capacity == 0 {
return;
}
if self.entries.contains_key(&key) {
self.touch(key); // an update counts as a use
self.entries.get_mut(&key).unwrap().0 = value;
return;
}
if self.entries.len() == self.capacity {
let bucket = self.buckets.get_mut(&self.min_freq).unwrap();
let victim = bucket.remove(0); // oldest use among the least frequent
if bucket.is_empty() {
self.buckets.remove(&self.min_freq);
}
self.entries.remove(&victim);
}
self.entries.insert(key, (value, 1));
self.buckets.entry(1).or_insert_with(Vec::new).push(key);
self.min_freq = 1; // a brand-new key always has the lowest frequency
}
}
/** LC 460. Key -> node map + one recency list per frequency + minFreq, which resets to 1 on every insert. */
export class LFUCache {
private nodeOf = new Map<number, CacheNode>();
private bucketOf = new Map<number, RecencyList>(); // frequency -> recency list of keys used that often
private minFreq = 0;
private capacity: number;
constructor(capacity: number) {
this.capacity = capacity;
}
private bucket(freq: number): RecencyList {
let list = this.bucketOf.get(freq);
if (list === undefined) {
list = new RecencyList();
this.bucketOf.set(freq, list);
}
return list;
}
private touch(node: CacheNode): void {
this.bucket(node.freq).remove(node);
// minFreq only advances when an access empties the exact bucket it points at
if (node.freq === this.minFreq && this.bucket(node.freq).size === 0) this.minFreq++;
node.freq++;
this.bucket(node.freq).addFirst(node);
}
get(key: number): number {
const node = this.nodeOf.get(key);
if (node === undefined) return -1;
this.touch(node);
return node.value;
}
put(key: number, value: number): void {
if (this.capacity === 0) return;
const existing = this.nodeOf.get(key);
if (existing !== undefined) {
existing.value = value;
this.touch(existing);
return;
}
if (this.nodeOf.size === this.capacity) {
// least recent node within the least frequent bucket; recency breaks the frequency tie
this.nodeOf.delete(this.bucket(this.minFreq).popLast().key);
}
const node = new CacheNode(key, value); // freq starts at 1
this.nodeOf.set(key, node);
this.bucket(1).addFirst(node);
this.minFreq = 1; // a brand-new key is always the least frequent
}
}
// lfuNode is LFUCache's doubly linked node, carrying its key, value, and
// current frequency.
type lfuNode struct {
key, val, freq int
prev, next *lfuNode
}
// lfuBucket is one sentinel-bracketed recency list holding every key of a
// single frequency, most recent right after front.
type lfuBucket struct {
front, back *lfuNode
size int
}
func newLfuBucket() *lfuBucket {
front := &lfuNode{}
back := &lfuNode{}
front.next = back
back.prev = front
return &lfuBucket{front: front, back: back}
}
// LFUCache is LC 460: one recency bucket per frequency plus a minFreq
// pointer for O(1) eviction. minFreq resets to 1 on every insertion and only
// increments when an access drains the bucket it points at. O(1) per op.
type LFUCache struct {
capacity, minFreq int
nodeOf map[int]*lfuNode
buckets map[int]*lfuBucket
}
func newLFUCache(capacity int) *LFUCache {
return &LFUCache{capacity: capacity, nodeOf: map[int]*lfuNode{}, buckets: map[int]*lfuBucket{}}
}
func (c *LFUCache) pushFront(node *lfuNode) {
bucket, ok := c.buckets[node.freq]
if !ok {
bucket = newLfuBucket()
c.buckets[node.freq] = bucket
}
node.prev = bucket.front
node.next = bucket.front.next
bucket.front.next.prev = node
bucket.front.next = node
bucket.size++
}
func (c *LFUCache) remove(node *lfuNode) {
node.prev.next = node.next
node.next.prev = node.prev
bucket := c.buckets[node.freq]
bucket.size--
if bucket.size == 0 {
delete(c.buckets, node.freq)
}
}
func (c *LFUCache) bump(node *lfuNode) {
c.remove(node)
if c.buckets[node.freq] == nil && c.minFreq == node.freq {
c.minFreq = node.freq + 1 // the bumped key lands in freq+1, so this stays valid
}
node.freq++
c.pushFront(node)
}
func (c *LFUCache) get(key int) int {
node, ok := c.nodeOf[key]
if !ok {
return -1
}
c.bump(node)
return node.val
}
func (c *LFUCache) put(key int, value int) {
if c.capacity <= 0 {
return
}
if node, ok := c.nodeOf[key]; ok {
node.val = value
c.bump(node) // an update bumps frequency too
return
}
if len(c.nodeOf) == c.capacity {
stale := c.buckets[c.minFreq].back.prev // least recent within the lowest frequency
c.remove(stale)
delete(c.nodeOf, stale.key)
}
node := &lfuNode{key: key, val: value, freq: 1}
c.nodeOf[key] = node
c.pushFront(node)
c.minFreq = 1 // a brand-new key is always the least frequent
}
// LC 460. One recency list (most recent at the front) per frequency bucket
// plus a key-to-node map and a minFreq pointer. Each access moves its node to
// the front of the next bucket; minFreq resets to 1 on every insertion and
// only increments when an access drains the bucket it points at.
class LFUCache {
class FreqNode {
var key: Int
var val: Int
var freq: Int
var prev: FreqNode?
var next: FreqNode?
init(_ key: Int, _ val: Int, _ freq: Int) {
self.key = key
self.val = val
self.freq = freq
}
}
class Bucket { // sentinel-ended recency list, most recent at the front
let front = FreqNode(0, 0, 0)
let back = FreqNode(0, 0, 0)
var count = 0
init() {
front.next = back
back.prev = front
}
func pushFront(_ node: FreqNode) {
node.prev = front
node.next = front.next
front.next!.prev = node
front.next = node
count += 1
}
func unlink(_ node: FreqNode) {
node.prev!.next = node.next
node.next!.prev = node.prev
count -= 1
}
}
let capacity: Int
var minFreq = 0
var bucketOf: [Int: Bucket] = [:] // freq -> recency list
var nodeOf: [Int: FreqNode] = [:]
init(_ capacity: Int) { self.capacity = capacity }
func bump(_ node: FreqNode) {
let freq = node.freq
bucketOf[freq]!.unlink(node)
if bucketOf[freq]!.count == 0 {
bucketOf[freq] = nil
if minFreq == freq { minFreq = freq + 1 } // the bumped key lands in freq + 1
}
node.freq = freq + 1
if bucketOf[freq + 1] == nil { bucketOf[freq + 1] = Bucket() }
bucketOf[freq + 1]!.pushFront(node)
}
func get(_ key: Int) -> Int {
guard let node = nodeOf[key] else { return -1 }
bump(node)
return node.val
}
func put(_ key: Int, _ value: Int) {
if capacity <= 0 { return }
if let node = nodeOf[key] {
node.val = value
bump(node) // an update counts as an access
return
}
if nodeOf.count == capacity {
let lowestBucket = bucketOf[minFreq]!
let stale = lowestBucket.back.prev! // least recent within the lowest frequency
lowestBucket.unlink(stale)
if lowestBucket.count == 0 { bucketOf[minFreq] = nil }
nodeOf[stale.key] = nil
}
let node = FreqNode(key, value, 1)
nodeOf[key] = node
if bucketOf[1] == nil { bucketOf[1] = Bucket() }
bucketOf[1]!.pushFront(node)
minFreq = 1 // a brand-new key is always the least frequent
}
}
13. Merge K Sorted Lists
Hard · LC 23
Given an array of k sorted linked lists, merge them into one sorted list and return its head. Push each non-null head into a min-heap keyed by node value, then repeatedly pop the smallest node, append it to a dummy-headed tail, and push that node's next if it exists. Every pop is O(log k) over n total nodes, giving O(n log k); the pairwise divide and conquer merge achieves the same bound without a heap.
def merge_k_lists(lists: "list[ListNode | None]") -> "ListNode | None":
"""LC 23. Merge K Sorted Lists.
Push each non-null head into a min-heap as a (val, tie, node)
triple, then repeatedly pop the smallest node, splice it behind a
dummy-headed tail, and push that node's next if it exists. The tie
is the source list's index, which keeps the heap from ever
comparing ListNode objects on equal values. n total nodes, each
pushed and popped once: O(n log k) time, O(k) space.
"""
frontier: "list[tuple[int, int, ListNode]]" = []
for tie, node in enumerate(lists):
if node:
frontier.append((node.val, tie, node))
heapq.heapify(frontier)
dummy_head = ListNode()
tail = dummy_head
while frontier:
_, tie, node = heapq.heappop(frontier)
tail.next = node
tail = node
if node.next:
# at most one node per source list is in flight, so ties never collide
heapq.heappush(frontier, (node.next.val, tie, node.next))
return dummy_head.next
// LC 23. Min-heap on node values seeded with each non-null head; pop the
// smallest, append it to a dummy-headed tail, push its successor. n total
// nodes, heap of at most k: O(n log k).
ListNode* mergeKLists(vector<ListNode*> lists) {
auto laterValue = [](ListNode* a, ListNode* b) { return a->val > b->val; }; // min-heap
priority_queue<ListNode*, vector<ListNode*>, decltype(laterValue)> minHeap(laterValue);
for (ListNode* head : lists)
if (head) minHeap.push(head);
ListNode dummy(0);
ListNode* tail = &dummy;
while (!minHeap.empty()) {
ListNode* smallest = minHeap.top();
minHeap.pop();
tail->next = smallest;
tail = smallest;
if (smallest->next) minHeap.push(smallest->next);
}
return dummy.next;
}
/// LC 23. BinaryHeap is a max-heap, so push Reverse((val, list_index)) to
/// pop the smallest live head in O(log k). Each pop detaches that list's
/// head onto the output tail and pushes the list's next head if any --
/// n total pops over at most k heap entries: O(n log k).
pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
let mut heap: BinaryHeap<Reverse<(i32, usize)>> = BinaryHeap::new();
for (i, list) in lists.iter().enumerate() {
if let Some(node) = list {
heap.push(Reverse((node.val, i)));
}
}
let mut dummy = Box::new(ListNode::new(0));
let mut tail = &mut dummy;
while let Some(Reverse((_, i))) = heap.pop() {
let mut node = lists[i].take().unwrap();
lists[i] = node.next.take();
if let Some(next) = &lists[i] {
heap.push(Reverse((next.val, i)));
}
tail.next = Some(node);
tail = tail.next.as_mut().unwrap();
}
dummy.next
}
/** LC 23. Min-heap of k list heads: pop the smallest, append it, push its next; O(n log k) total. */
export function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
// inline binary min-heap on node values, backed by a plain array
const heap: ListNode[] = [];
const push = (node: ListNode): void => {
heap.push(node);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent].val <= heap[child].val) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): ListNode => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let smallest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left].val < heap[smallest].val) smallest = left;
if (right < heap.length && heap[right].val < heap[smallest].val) smallest = right;
if (smallest === parent) break;
[heap[parent], heap[smallest]] = [heap[smallest], heap[parent]];
parent = smallest;
}
}
return top;
};
for (const head of lists) if (head !== null) push(head);
const dummy = new ListNode();
let tail = dummy;
while (heap.length > 0) {
const smallest = pop();
tail.next = smallest;
tail = smallest;
if (smallest.next !== null) push(smallest.next); // the winning list refills the heap with its next node
}
return dummy.next;
}
// LC 23. Min-heap of the k frontiers: pop the smallest node, splice it behind
// a dummy-headed tail, push its successor. n total nodes, heap of at most k:
// O(n log k).
func mergeKLists(lists []*ListNode) *ListNode {
heap := []*ListNode{}
siftUp := func(i int) {
for i > 0 {
parent := (i - 1) / 2
if heap[parent].Val <= heap[i].Val {
break
}
heap[parent], heap[i] = heap[i], heap[parent]
i = parent
}
}
siftDown := func(i int) {
for {
smallest := i
if left := 2*i + 1; left < len(heap) && heap[left].Val < heap[smallest].Val {
smallest = left
}
if right := 2*i + 2; right < len(heap) && heap[right].Val < heap[smallest].Val {
smallest = right
}
if smallest == i {
return
}
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
}
}
push := func(node *ListNode) {
heap = append(heap, node)
siftUp(len(heap) - 1)
}
pop := func() *ListNode {
smallest := heap[0]
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
if len(heap) > 0 {
siftDown(0)
}
return smallest
}
for _, head := range lists {
if head != nil {
push(head)
}
}
dummy := &ListNode{}
tail := dummy
for len(heap) > 0 {
smallest := pop()
tail.Next = smallest
tail = smallest
if smallest.Next != nil {
push(smallest.Next)
}
}
return dummy.Next
}
// LC 23. Min-heap of the k list frontiers: pop the smallest node, splice it
// behind a dummy-headed tail, push its successor. n total nodes through a
// heap of at most k: O(n log k).
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
var heap: [ListNode] = [] // array-backed binary min-heap on node values
func push(_ node: ListNode) {
heap.append(node)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent].val <= heap[child].val { break }
heap.swapAt(parent, child)
child = parent
}
}
func popMin() -> ListNode {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var smallest = parent
for child in [2 * parent + 1, 2 * parent + 2]
where child < heap.count && heap[child].val < heap[smallest].val {
smallest = child
}
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
return top
}
for head in lists {
if let head = head { push(head) }
}
let dummy = ListNode()
var tail = dummy
while !heap.isEmpty {
let smallest = popMin()
tail.next = smallest
tail = smallest
if let after = smallest.next { push(after) }
}
return dummy.next
}
14. Reverse Nodes In K Group
Hard · LC 25
Given a list and an integer k, reverse every group of k consecutive nodes, leaving a final shorter group untouched, and return the head. From a dummy node, first probe k nodes ahead to confirm a full group, reverse that block with the usual three-pointer walk, then splice it back between the neighbors. Probing before reversing protects the short tail, and the group's original first node becomes its tail, anchoring the next splice.
def reverse_k_group(head: "ListNode | None", k: int) -> "ListNode | None":
"""LC 25. Reverse Nodes in K Group.
From a dummy node, probe k nodes ahead to confirm a full group
before touching anything, reverse that block with the usual
three-pointer walk, then splice it back between its neighbors.
Probing first is what leaves a short tail untouched, and the
group's original first node becomes its tail, anchoring the next
splice. O(n) time, O(1) space.
"""
dummy_head = ListNode(0, head)
group_anchor = dummy_head # last node of the previous, already-final group
while True:
probe = group_anchor
for _ in range(k):
probe = probe.next
if not probe:
return dummy_head.next # fewer than k left: leave them in order
group_tail = group_anchor.next # the first node sinks to the group's tail
prev = probe.next # seeding with the node after the group pre-splices the far seam
cur = group_anchor.next
for _ in range(k):
following = cur.next
cur.next = prev
prev = cur
cur = following
group_anchor.next = prev # prev is the reversed group's new first node
group_anchor = group_tail
// LC 25. From a dummy, probe k nodes ahead before touching anything so a
// short tail stays untouched, reverse the block with the usual three-pointer
// walk aimed at the node after the group, then splice. The group's original
// first node becomes its tail, anchoring the next splice.
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0);
dummy.next = head;
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = groupPrev;
for (int i = 0; i < k && kth; ++i) kth = kth->next; // probe before reversing
if (!kth) break; // leftover shorter than k is left as is
ListNode* groupNext = kth->next;
ListNode* prev = groupNext; // reversed block links straight into the rest
ListNode* cur = groupPrev->next;
while (cur != groupNext) {
ListNode* after = cur->next;
cur->next = prev;
prev = cur;
cur = after;
}
ListNode* groupTail = groupPrev->next; // original first node, now the block's tail
groupPrev->next = kth;
groupPrev = groupTail;
}
return dummy.next;
}
/// LC 25. From an anchor before each group, probe k nodes ahead first so a
/// short final group stays untouched. A full group is detached whole,
/// reversed with the usual take/relink walk, and spliced back; the group's
/// original first node surfaces as the block tail, so walking the anchor
/// k steps lands on it, ready to reattach the remainder and anchor the
/// next splice.
pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode { val: 0, next: head });
let mut anchor = &mut dummy;
'groups: loop {
let mut probe = anchor.next.as_ref();
for _ in 0..k {
match probe {
Some(node) => probe = node.next.as_ref(),
None => break 'groups, // fewer than k left: leftover keeps its order
}
}
let mut rest = anchor.next.take();
let mut reversed = None;
for _ in 0..k {
let mut node = rest.unwrap();
rest = node.next.take();
node.next = reversed;
reversed = Some(node);
}
anchor.next = reversed;
for _ in 0..k {
anchor = anchor.next.as_mut().unwrap();
}
anchor.next = rest;
}
dummy.next
}
/** LC 25. Probe k ahead to confirm a full group, reverse the block, splice it back between its neighbors. */
export function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
const dummy = new ListNode(0, head);
let groupAnchor = dummy; // last node of the previous, already finished section
for (;;) {
// probing before reversing is what protects a short final group
let kth: ListNode | null = groupAnchor;
for (let step = 0; step < k && kth !== null; step++) kth = kth.next;
if (kth === null) break;
const groupNext = kth.next;
// usual three-pointer reversal, but prev starts at groupNext so the group tail links forward
let prev: ListNode | null = groupNext;
let cur = groupAnchor.next;
while (cur !== groupNext) {
const next: ListNode | null = cur!.next;
cur!.next = prev;
prev = cur;
cur = next;
}
const groupTail = groupAnchor.next!; // the group's original first node is now its tail
groupAnchor.next = kth; // kth is the group's new first node
groupAnchor = groupTail; // and the tail anchors the next splice
}
return dummy.next;
}
// LC 25. Probe k ahead before touching anything so a short tail stays in
// order, reverse the block aimed at the node after the group, then splice;
// the group's original first node becomes its tail, anchoring the next splice.
func reverseKGroup(head *ListNode, k int) *ListNode {
dummy := &ListNode{Next: head}
groupPrev := dummy
for {
kth := groupPrev
for i := 0; i < k && kth != nil; i++ { // probe before reversing
kth = kth.Next
}
if kth == nil {
break // leftover shorter than k is left as is
}
groupNext := kth.Next
prev := groupNext // reversed block links straight into the rest
cur := groupPrev.Next
for cur != groupNext {
after := cur.Next
cur.Next = prev
prev = cur
cur = after
}
groupTail := groupPrev.Next // original first node, now the block's tail
groupPrev.Next = kth
groupPrev = groupTail
}
return dummy.Next
}
// LC 25. From a dummy, probe k nodes ahead before touching anything so a
// short tail stays untouched, reverse the block with the usual three-pointer
// walk aimed at the node after the group, then splice. The group's original
// first node becomes its tail, anchoring the next splice.
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
let dummy = ListNode(0, head)
var groupAnchor = dummy // last node of the previous, already-final group
while true {
var probe: ListNode? = groupAnchor
for _ in 0..<k {
probe = probe?.next
if probe == nil { return dummy.next } // fewer than k left: leave them in order
}
let groupTail = groupAnchor.next! // the first node sinks to the group's tail
var prev = probe!.next // seeding with the node after the group pre-splices the far seam
var cur = groupAnchor.next
for _ in 0..<k {
let after = cur!.next
cur!.next = prev
prev = cur
cur = after
}
groupAnchor.next = prev // prev is the reversed group's new first node
groupAnchor = groupTail
}
}