Linked Lists, Stacks, and Queues Questions

Approach:
Traverse the linked list while consuming group sizes from the given array. For each group size k_i, if there are at least k_i nodes remaining, reverse that contiguous group in-place using classic pointer reversal; otherwise leave the remaining nodes as-is. Maintain prev_tail (node before current group) to reconnect reversed groups and head update for the first group.

Code (Python):

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_k_nodes(start, k):
    """
    Reverse exactly k nodes starting at start.
    Returns (new_head, new_tail, next_node_after_group)
    Assumes there are at least k nodes starting at start.
    """
    prev = None
    cur = start
    cnt = 0
    while cnt < k:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
        cnt += 1
    # prev is new head of reversed group, start is new tail
    return prev, start, cur

def reverse_variable_groups(head, groups):
    """
    Reverse list in-place for each group size in groups.
    Only reverse a group if there are >= k nodes remaining.
    Returns new head.
    """
    dummy = ListNode(0, head)
    prev_tail = dummy
    cur = head
    gi = 0
    while cur and gi < len(groups):
        k = groups[gi]
        if k <= 0:
            gi += 1
            continue  # skip non-positive sizes
        # check if enough nodes remain
        node = cur
        count = 0
        while node and count < k:
            node = node.next
            count += 1
        if count < k:
            break  # leave the remaining nodes as-is
        new_head, new_tail, next_node = reverse_k_nodes(cur, k)
        # reconnect
        prev_tail.next = new_head
        new_tail.next = next_node
        prev_tail = new_tail
        cur = next_node
        gi += 1
    return dummy.next

Correctness reasoning:

• For each group we verify there are at least k nodes; reversing exactly k nodes is done via standard iterative in-place reversal, which preserves connectivity because we return the new head/tail and the next pointer. Reconnecting prev_tail.next and new_tail.next maintains list integrity. We handle the first group's head by using a dummy node.

Time & Space complexity:

• Time: O(n + m) where n is number of nodes and m = len(groups). The dominant cost is scanning nodes once overall (each node is visited a constant number of times: once when counting and once when reversed), so O(n).
• Space: O(1) extra space (in-place pointer manipulation, aside from input arrays and a few pointers).

Edge cases:

• groups contains zeros or negatives (we skip non-positive sizes).
• Remaining nodes fewer than required k: leave them as-is (alternative behavior could be to reverse partially—specify if needed).
• Empty list or empty groups array: return original head.
• Very large k values: counting step prevents invalid reversal.

Alternatives/trade-offs:

• If requirement asks to reverse the final partial group as well, change the check count<k to allow reversal of count nodes.
• One-pass optimization: avoid separate counting by attempting to reverse while detecting end early, but then must rollback partial reversal if insufficient nodes — counting-first is simpler and safer.

A circular buffer (ring buffer) is a fixed-size array used as a FIFO queue by treating the array as circular: when an index reaches the end it wraps to 0. It avoids moving elements by maintaining indices for head (pop position) and tail (push position). Two common ways to distinguish full vs empty:

• Maintain a size counter (size == 0 => empty, size == capacity => full).
• Or use capacity+1 and treat buffer as full when (tail + 1) % (capacity+1) == head (simpler boolean-free check).

Using the size approach (clear and intuitive), here is O(1) enqueue/dequeue pseudo-code in C++ style:

// Fixed-capacity circular buffer (no element moves)
template<typename T>
class RingBuffer {
public:
    RingBuffer(size_t capacity) : cap(capacity), buf(new T[capacity]), head(0), tail(0), sz(0) {}

    ~RingBuffer() { delete[] buf; }

    bool enqueue(const T& item) {
        if (sz == cap) return false; // full
        buf[tail] = item;
        tail = (tail + 1) % cap;
        ++sz;
        return true;
    }

    bool dequeue(T &out) {
        if (sz == 0) return false; // empty
        out = buf[head];
        head = (head + 1) % cap;
        --sz;
        return true;
    }

    bool empty() const { return sz == 0; }
    bool full() const { return sz == cap; }
    size_t size() const { return sz; }

private:
    size_t cap;
    T* buf;
    size_t head; // next to read
    size_t tail; // next to write
    size_t sz;   // current number of elements
};

Key points:

• Enqueue/dequeue are O(1): single assignment and index arithmetic.
• No element shifting; elements are overwritten only when explicitly allowed (after dequeue).
• Space: O(capacity). Edge cases: ensure capacity>0, handle wrap with modulo, and decide behavior on full (reject or overwrite).

To merge two sorted singly linked lists in-place iteratively, use a dummy head and advance pointers by reusing existing nodes (no new node allocations). Walk both lists, attach the smaller node to the tail, advance that list's pointer, and continue until one list is exhausted—then attach the remaining part.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def __repr__(self):
        return str(self.val)

def merge_two_sorted_lists(l1, l2):
    """
    Merge two sorted singly linked lists in-place.
    Time: O(n + m), Space: O(1)
    Returns head of merged list.
    """
    dummy = ListNode(-1)   # temporary starter
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
        tail.next = None  # detach to avoid accidental cycles

    # attach remaining nodes (one of l1 or l2 may be non-empty)
    tail.next = l1 if l1 else l2
    return dummy.next

# Example:
# l1: 1->3->5
l1 = ListNode(1, ListNode(3, ListNode(5)))
# l2: 2->4
l2 = ListNode(2, ListNode(4))

merged = merge_two_sorted_lists(l1, l2)

# Print result
out = []
cur = merged
while cur:
    out.append(str(cur.val))
    cur = cur.next
print("->".join(out))  # Output: 1->2->3->4->5

Key points:

• Uses only existing nodes (O(1) extra space).
• Deterministic O(n+m) time: each node visited once.
• Edge cases: one or both lists empty; duplicate values handled by <= branch.
• Alternative: recursive merge (elegant but uses O(n+m) call stack).

Monotonic stacks vs monotonic queues — core difference:

• Both maintain elements in monotonic order (increasing or decreasing) to allow O(1)-amortized access to extremes, but a monotonic stack enforces LIFO access (useful when you need to compare each element to previous ones and then “pop” them), while a monotonic queue supports FIFO order (useful for sliding windows where you must evict oldest elements as the window moves).

Problem 1 (monotonic stack): Next Greater Element / Largest Rectangle in Histogram

• Example: Next Greater Element to the right. Iterate left→right, keep a decreasing stack of indices whose elements haven’t yet found a greater element. For each new element x, pop indices whose value < x and record x as their next greater; then push current index.
• Why O(n): each index is pushed once and popped at most once → O(n) amortized.
• Brute force: for each element scan right until a greater one is found → worst-case O(n^2).

Problem 2 (monotonic queue): Sliding Window Maximum

• Maintain a deque of indices in decreasing order of values. For each new index i: remove from back all indices with smaller values, append i; remove from front if it’s outside the window; front holds the window max.
• Why O(n): each index enters and leaves deque at most once → O(n) total.
• Brute force: recompute max for each window by scanning k elements → O(n·k), potentially O(n^2) if k ~ n.

Key intuition: monotonic structures eliminate redundant comparisons by discarding elements that cannot influence future answers, converting nested scans into linear amortized work.

To reverse a sublist in one pass, use a dummy node to simplify edge cases, find the node right before position m (pre), then iteratively move nodes after the current start into the front of the reversed section (standard head-insertion technique). This uses O(1) extra space and one traversal.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_sublist(head, m, n):
    """
    Reverse nodes from position m to n (1-based) in-place, one pass.
    Returns new head.
    """
    if head is None or m >= n:
        return head

    # Validate m,n
    if m < 1 or n < 1:
        raise ValueError("Positions must be >= 1")
    
    dummy = ListNode(0, head)
    pre = dummy  # will point to node before position m

    # Move `pre` to node before m
    for _ in range(m - 1):
        if pre.next is None:
            raise IndexError("m out of bounds")
        pre = pre.next

    # `start` is the first node of the sublist to reverse
    start = pre.next
    if start is None:
        raise IndexError("m out of bounds")

    # Reverse by head-insertion for (n-m) times
    then = start.next
    for _ in range(n - m):
        if then is None:
            raise IndexError("n out of bounds")
        # Re-linking: move `then` node to after `pre`
        start.next = then.next      # detach `then`
        then.next = pre.next        # insert `then` at front of sublist
        pre.next = then
        then = start.next           # advance `then`

    return dummy.next

Key pointer updates during each iteration:

• start.next = then.next detaches the node being moved.
• then.next = pre.next places moved node at sublist front.
• pre.next = then connects moved node into list.
• then advances to next candidate via start.next.

Time: O(L) where L=length of list (single pass). Space: O(1). Edge cases: m==n (no-op), m or n out of bounds, empty list, reversing including head (handled by dummy).