Linked Lists, Stacks, and Queues Questions

Using sentinel (dummy) head/tail nodes means the list always has at least these placeholder nodes so real data nodes are never the absolute head or tail. This removes many special cases (empty list, insertion/deletion at head/tail) because operations can assume previous/next nodes exist.

Example (doubly linked list) — insert new node after a given node:

# sentinel.head and sentinel.tail exist; real nodes go between them
def insert_after(node, value):
    new = Node(value)
    new.prev = node
    new.next = node.next
    node.next.prev = new   # safe: node.next always exists (could be tail sentinel)
    node.next = new

Without sentinels you'd need checks like "if node is tail: update tail pointer" or "if list empty: set head and tail".

Deletion of a node:

def delete(node):
    # assume node is not a sentinel
    node.prev.next = node.next   # safe: prev exists
    node.next.prev = node.prev
    # optionally clear node.prev/node.next for GC

Without sentinels deleting the head requires updating head pointer and handling empty-list case; deleting the only node requires setting head=tail=None.

Concrete scenarios simplified:

• Pop front: with sentinel remove first real node at head.next; no if-empty check.
• Append: insert before tail sentinel; no need to update tail pointer.

Downsides and overhead:

• Memory: two extra nodes (O(1) extra memory), small compared to typical dataset sizes; negligible per-list but matters if creating millions of tiny lists.
• Slight complexity: sentinel nodes must be treated as non-data (filtering during traversal).
• Minor runtime: tiny constant overhead in checks/initialization.
  Overall benefit: much simpler, less error-prone code—especially valuable in production systems where correctness and maintainability matter.

To remove the first node with val == value, use a dummy (sentinel) node that points to the original head. The dummy simplifies handling when the head itself needs deletion and avoids special-casing head removal.

#include <stdlib.h>

struct Node {
    int val;
    struct Node* next;
};

void delete_first(struct Node** head, int value) {
    if (head == NULL || *head == NULL) return;

    // Create dummy that precedes the list
    struct Node dummy;
    dummy.next = *head;

    struct Node* prev = &dummy;
    struct Node* cur = dummy.next;

    while (cur != NULL) {
        if (cur->val == value) {
            // unlink and free
            prev->next = cur->next;
            free(cur);
            break; // only delete first occurrence
        }
        prev = cur;
        cur = cur->next;
    }

    // Update external head in case first node was removed
    *head = dummy.next;
}

Key points:

• Dummy avoids separate logic when deleting the head.
• We update *head from dummy.next after possible removal.
• Time complexity O(n), space O(1).
• Edge cases: empty list, value not found, single-node list. Ensure callers don't use freed nodes.

Approach: Use two pointers pa and pb starting at headA and headB. Advance each one step at a time; when a pointer reaches NULL, switch it to the other list's head. They will either meet at the intersection node or both become NULL after traversing m+n steps. This equalizes distances without extra space.

// C++ implementation
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(nullptr) {}
};

ListNode* intersection_node(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return nullptr;
    ListNode *pa = headA, *pb = headB;
    // After at most m + n steps, pa == pb (either intersection node or nullptr)
    while (pa != pb) {
        pa = pa ? pa->next : headB;
        pb = pb ? pb->next : headA;
    }
    return pa; // could be nullptr or intersection node
}

Why pointer switching works:

• Let lengths be m and n, with shared tail length c if intersecting. Distinct parts are m-c and n-c.
• If pointers traverse their lists then switch, pa travels (m-c) + c + n steps; pb travels (n-c) + c + m steps. Both travel m+n-c+c = m+n steps before first alignment. If an intersection exists they arrive at the same node at the same time; otherwise both become NULL after m+n steps.
  Key points:
• Time: O(m + n)
• Space: O(1)
  Edge cases:
• One or both heads NULL
• No intersection (returns NULL)
• Lists of very different lengths handled by switching technique.

Approach: Find middle (fast/slow), reverse second half in-place, compare first and reversed second half, then restore second half by reversing back. This is O(n) time, O(1) extra space and returns the list to original form.

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v=0): val(v), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* nxt = head->next;
        head->next = prev;
        prev = head;
        head = nxt;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    // Find middle
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // Reverse second half
    ListNode* second = reverseList(slow->next);
    ListNode* first = head;
    ListNode* p2 = second;
    bool pal = true;
    while (p2) {
        if (first->val != p2->val) { pal = false; break; }
        first = first->next;
        p2 = p2->next;
    }
    // Restore list
    slow->next = reverseList(second);
    return pal;
}

Key points:

• Finding middle with slow/fast handles both even/odd lengths.
• Reversing in-place uses constant extra memory.
• Time: O(n) (each node touched constant times). Space: O(1) extra.
• Edge cases: empty list, single node, even/odd length, duplicates.

Why restore? In long-running systems data structures may be shared, cached, or relied on by other components; leaving them mutated can cause hard-to-debug state corruption, incorrect downstream processing, and violate data contracts. Restoring preserves invariants and enables safe reuse.

Approach: iterate the list, reversing each contiguous block of k nodes in-place using pointer manipulation. Use a dummy head for easy head changes, check there are k nodes ahead before reversing, reverse by standard iterative node-relinking, then reconnect reversed block to list. O(1) extra space, O(n) time.

// C++ implementation
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr) {}
};

ListNode* reverse_k_group(ListNode* head, int k) {
    if (!head || k <= 1) return head;
    ListNode dummy(0);
    dummy.next = head;
    ListNode* group_prev = &dummy;

    while (true) {
        // Check if there are k nodes ahead
        ListNode* kth = group_prev;
        for (int i = 0; i < k && kth; ++i) kth = kth->next;
        if (!kth) break; // fewer than k nodes remain

        ListNode* group_start = group_prev->next;
        ListNode* next_group = kth->next;

        // Reverse [group_start .. kth]
        ListNode* prev = next_group;
        ListNode* curr = group_start;
        while (curr != next_group) {
            ListNode* tmp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tmp;
        }

        // Connect reversed group back
        group_prev->next = kth;      // kth is new head of this group
        group_prev = group_start;    // group_start is now tail after reversal
    }

    return dummy.next;
}

Key points:

• We reverse nodes by moving pointers only; no extra arrays or recursion.
• prev initialized to next_group so tail points to remainder.
  Time: O(n) — each node touched constant times. Space: O(1).
  Edge cases: k <= 1, empty list, list length not multiple of k (left as-is). Alternative: recursive solution (cleaner but uses O(n/k) stack).