Linked List Interview Problems for Embedded Engineers

Key Insight: You only need three pointers to reverse a linked list in a single pass. At each node, save the next pointer, reverse the current link, then advance. The previous pointer ends up at the new head.

Thought Process:

1. Recursive approach would be O(n) space due to call stack — not ideal for embedded.
2. Iterative: maintain pre, cur, and nxt. At each step, cur->next = pre reverses the link.
3. After the loop, cur is null and pre points to the last node visited — the new head.
4. Edge cases: empty list or single node — return head immediately (no work needed).

Time Complexity: O(n) — single pass through all nodes. Space Complexity: O(1) — three pointers regardless of list size.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode *pre = nullptr, *cur = head, *nxt;

        while (cur) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};

Embedded relevance: Reversing a linked list in-place is the building block for reordering RTOS task priority queues and reversing message buffers without extra memory allocation.

Key Insight: Two pointers moving at different speeds will eventually meet if there is a cycle — the fast pointer "laps" the slow pointer. If there is no cycle, the fast pointer reaches null first.

Thought Process:

1. Hash set approach: store visited node addresses, check for repeats — O(n) time but O(n) space. Not suitable for embedded.
2. Floyd's tortoise-and-hare: slow moves 1 step, fast moves 2 steps. If a cycle exists, fast enters the cycle first and eventually catches slow from behind.
3. Why do they always meet? Once both are in the cycle, the gap between them decreases by 1 each step (fast gains 1 step per iteration). They must meet within one full cycle traversal.
4. Termination: if fast reaches null (or fast->next is null), no cycle exists.

Time Complexity: O(n) — fast pointer traverses at most 2n nodes total. Space Complexity: O(1) — two pointers.

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;

        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

Embedded relevance: Cycle detection is critical in embedded systems for validating linked data structures in memory — a corrupted pointer can create a cycle that causes an infinite loop, hanging the system.

Key Insight: You cannot actually remove the given node from the list (no access to the previous node). Instead, copy the next node's value into the current node, then skip over the next node. The current node "becomes" its successor.

Thought Process:

1. Normally, deletion in a singly linked list requires the previous node to re-link around the deleted node. But we only have the node itself.
2. Trick: overwrite the current node's value with the next node's value, then delete the next node by pointing node->next past it.
3. Caveat: this changes the node identity — any external pointers to the original next node now point to a freed node. Interviewers may ask about this tradeoff.
4. This only works for non-tail nodes (the problem guarantees the node is not the tail).

Time Complexity: O(1) — constant-time pointer manipulation. Space Complexity: O(1) — no extra storage.

class Solution {
public:
    void deleteNode(ListNode* node) {
        if (!node || !node->next) return;
        node->val = node->next->val;
        ListNode* toDelete = node->next;
        node->next = node->next->next;
        delete toDelete;
    }
};

Embedded relevance: This copy-and-skip trick appears in intrusive linked lists used by RTOS kernels — where nodes are embedded inside task control blocks and you cannot always traverse from the head.

Key Insight: Since the list is sorted, all duplicates are adjacent. Walk through comparing each node to its predecessor — when values differ, link the unique node into the result; when they match, skip the duplicate.

Thought Process:

1. If the list were unsorted, we would need a hash set to track seen values — O(n) space. But sorted order guarantees duplicates cluster together.
2. Use two pointers: pre tracks the last unique value seen, cur scans ahead. When cur->val != pre->val, link cur into the de-duplicated list.
3. After the loop, terminate the result list by setting dummy->next = cur (null) to cut off any trailing duplicates.
4. The head never changes (first node is always unique), so no dummy head is needed for this variant.

Time Complexity: O(n) — single pass through all nodes. Space Complexity: O(1) — two pointers.

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *dummy, *pre, *cur;
        if (!head || !head->next) return head;

        dummy = pre = head;
        cur = head->next;

        while (cur) {
            if (pre->val != cur->val) {
                dummy->next = cur;
                dummy = cur;
            }
            pre = cur;
            cur = cur->next;
        }
        dummy->next = cur;
        return head;
    }
};

Embedded relevance: Deduplication of sorted sensor readings is common when processing time-series data from ADCs — removing redundant samples before storing to flash or transmitting over a low-bandwidth link.

Key Insight: A dummy head node eliminates the special case of choosing which list provides the first node. After the dummy, simply compare heads and append the smaller one — the logic is uniform throughout.

Thought Process:

1. Without a dummy node, you need an if/else to determine which list's head becomes the merged list's head. A dummy node makes the first append identical to all subsequent appends.
2. At each step, compare l1->val and l2->val, append the smaller node to dummy, and advance that list's pointer.
3. When one list is exhausted, append the entire remainder of the other — no need to copy node by node since the tail is already sorted.
4. Return head.next to skip the dummy node.

Time Complexity: O(n + m) — each node from both lists is visited exactly once. Space Complexity: O(1) — the dummy node is stack-allocated; no heap allocation.

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;

        ListNode head(0);
        ListNode* dummy = &head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                dummy->next = l1;
                l1 = l1->next;
            } else {
                dummy->next = l2;
                l2 = l2->next;
            }
            dummy = dummy->next;
        }
        dummy->next = (l1) ? l1 : l2;
        return head.next;
    }
};

Embedded relevance: Merging sorted lists is the core operation in merge sort — the preferred sorting algorithm for linked data in embedded systems because it is stable, O(n log n), and requires no random access.

Key Insight: This is a composite problem that chains three linked list techniques: (1) find the middle with slow/fast pointers, (2) reverse the second half in-place, (3) compare both halves node by node.

Thought Process:

1. Brute force: copy values to an array, check array palindrome — O(n) space. Fails the O(1) space constraint.
2. Can we compare without extra storage? If we reverse the second half of the list, we can walk two pointers from both ends toward the middle.
3. Step 1: find the middle with slow/fast. Step 2: reverse from slow to the end. Step 3: compare the original first half and the reversed second half.
4. For odd-length lists, the middle node is compared against itself (always matches), so no special case is needed.

Time Complexity: O(n) — three O(n) passes (find middle, reverse, compare). Space Complexity: O(1) — in-place reversal, two comparison pointers.

class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode *pre = nullptr, *cur = head, *nxt;
        while (cur) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;

        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode *rev = reverse(slow);
        while (rev) {
            if (rev->val != head->val) return false;
            rev = rev->next;
            head = head->next;
        }
        return true;
    }
};

Embedded relevance: The pattern of splitting a data stream, processing each half independently, and comparing results mirrors how redundant sensor channels are validated — process both readings and compare for consistency.

Key Insight: A dummy node before the head handles the tricky case where the head itself needs to be removed. Without a dummy, you would need separate logic for removing head nodes vs. interior nodes.

Thought Process:

1. If the head matches val, the head must change. This is awkward to handle without a dummy node.
2. With a dummy: iterate through the list with pre and cur. If cur->val == val, skip it. Otherwise, link it into the result via pre->next = cur.
3. After the loop, set pre->next = nullptr to terminate the result list (handles trailing matches).
4. Return dummy.next — which is the new head after all removals.

Time Complexity: O(n) — single pass through all nodes. Space Complexity: O(1) — dummy node on the stack, two pointers.

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy;
        dummy.next = head;
        ListNode *pre = &dummy, *cur = head;

        while (cur) {
            if (cur->val == val) {
                cur = cur->next;
            } else {
                pre->next = cur;
                cur = cur->next;
                pre = pre->next;
            }
        }
        pre->next = cur;
        return dummy.next;
    }
};

Embedded relevance: Removing specific elements from a linked list mirrors how RTOS event queues filter out cancelled or expired events — walking the queue and unlinking matching entries without disturbing the rest.

Key Insight: If two lists intersect, they share a common tail. The intersection point is missed when traversing both from their heads because the lists have different lengths. Advance the longer list by the length difference so both pointers are equidistant from the intersection.

Thought Process:

1. Hash set approach: store all nodes from list A, walk list B checking for matches — O(n + m) time but O(n) space.
2. Length-based approach: count both lengths, advance the longer list by |lenA - lenB| steps, then walk both in lockstep. The first node where they point to the same address is the intersection.
3. Compare by pointer identity (longer == shorter), not by value — two nodes can have the same value without being the same node.
4. If no intersection exists, both pointers reach null simultaneously.

Time Complexity: O(n + m) — two passes to count lengths, one pass to find intersection. Space Complexity: O(1) — four pointers and two counters.

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (!headA || !headB) return nullptr;

        int lenA = 0, lenB = 0;
        ListNode *A = headA, *B = headB;
        while (A) { lenA++; A = A->next; }
        while (B) { lenB++; B = B->next; }

        int diff = abs(lenA - lenB);
        ListNode *longer = lenA > lenB ? headA : headB;
        ListNode *shorter = lenA > lenB ? headB : headA;
        while (diff--) longer = longer->next;

        while (longer && shorter) {
            if (longer == shorter) return longer;
            longer = longer->next;
            shorter = shorter->next;
        }
        return nullptr;
    }
};

Embedded relevance: Detecting shared data structure nodes is important in memory pool debugging — finding where two allocation chains merge can reveal double-free bugs or unintended aliasing.

Key Insight: You don't need to know the length first. The slow/fast pointer technique finds the middle in a single pass — no counting, no second traversal.

Thought Process:

1. Naive approach: traverse once to count length, then traverse again to length/2. Two passes.
2. Better: use two pointers. Slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle.
3. Why does slow land on the second middle for even-length lists? Because both pointers start at head. If fast started at head->next, slow would land on the first middle instead.
4. The termination condition fast != NULL && fast->next != NULL handles both odd and even lengths cleanly.

Time Complexity: O(n) — single pass (fast pointer traverses the full list). Space Complexity: O(1) — two pointers.

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

Embedded relevance: The slow/fast pointer pattern is used in circular buffer overflow detection — checking if a producer pointer has lapped a consumer pointer without maintaining a separate count variable.

Key Insight: This is a shift register in software. As you traverse the list, each new bit arrives from the MSB side. Left-shift the accumulator and OR in the new bit — exactly what a serial-in parallel-out (SIPO) shift register does in hardware.

Thought Process:

1. The list gives us bits MSB-first. We need to build the number incrementally.
2. At each node: the existing accumulated value needs to "make room" for the new bit by shifting left, then the new bit is placed in the lowest position via OR.
3. num = (num << 1) | head->val — this is the core operation. It works for any starting value of num (initialized to 0).
4. No need to know the list length in advance — the shift-and-OR naturally handles any length.

Time Complexity: O(n) — single traversal. Space Complexity: O(1) — single integer accumulator.

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int num = 0;
        while (head != nullptr) {
            num = (num << 1) | head->val;
            head = head->next;
        }
        return num;
    }
};

Embedded relevance: This is exactly how a SIPO shift register works — bits arrive one at a time (MSB first), shifted into a register that accumulates the full word. Used in SPI receive paths and serial protocol decoders.

Key Insight: A singly linked list naturally supports O(1) removal from the front (head) and O(1) insertion at the back — if you maintain a tail pointer. Without a tail pointer, enqueue would be O(n) because you would have to walk to the end every time.

Thought Process:

1. Queue needs FIFO: enqueue at the back, dequeue from the front.
2. Singly linked list gives O(1) removal from head (just advance head). But insertion at the tail is O(n) without a tail pointer.
3. Solution: maintain both head and tail pointers. Enqueue links a new node at tail->next and advances tail. Dequeue advances head.
4. Edge case: when the queue becomes empty after a dequeue, reset tail to null as well. When enqueueing into an empty queue, both head and tail point to the new node.

Time Complexity: O(1) per operation — enqueue, dequeue, peek, and isEmpty are all constant time. Space Complexity: O(n) — one node per element in the queue.

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Queue {
    ListNode* head;
    ListNode* tail;

public:
    Queue() : head(nullptr), tail(nullptr) {}

    void enqueue(int val) {
        ListNode* node = new ListNode(val);
        if (!tail) {
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }

    int dequeue() {
        if (!head) return -1; // or throw
        int val = head->val;
        ListNode* tmp = head;
        head = head->next;
        if (!head) tail = nullptr;
        delete tmp;
        return val;
    }

    int peek() {
        return head ? head->val : -1;
    }

    bool isEmpty() {
        return head == nullptr;
    }
};

Embedded relevance: Linked-list queues are the backbone of RTOS message passing — FreeRTOS xQueueSend/xQueueReceive and Zephyr k_msgq use similar structures internally for inter-task communication with O(1) enqueue/dequeue.

Key Insight: This problem decomposes into three sub-problems you already know: (1) find the middle, (2) reverse the second half, (3) interleave-merge the two halves. Each step uses a fundamental linked list technique.

Thought Process:

1. Brute force: copy values to an array, rearrange, copy back — O(n) space. We want O(1).
2. Observation: the reordered list interleaves the first half with the reversed second half. So split, reverse, and merge.
3. Step 1: slow/fast to find the middle. Step 2: reverse from slow->next onward. Step 3: alternate nodes from both halves.
4. Cut the first half from the second by setting slow->next = NULL after finding the middle. This prevents an infinite loop during the merge.

Time Complexity: O(n) — three linear passes (find middle, reverse, merge). Space Complexity: O(1) — all operations are in-place.

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head) return;

        // Step 1: Find middle
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse second half
        ListNode *prev = NULL, *cur = slow->next, *save;
        while (cur) {
            save = cur->next;
            cur->next = prev;
            prev = cur;
            cur = save;
        }
        slow->next = NULL;

        // Step 3: Interleave merge
        ListNode *head2 = prev;
        while (head2) {
            save = head->next;
            head->next = head2;
            head = head2;
            head2 = save;
        }
    }
};

Embedded relevance: Interleaving two data streams is common in embedded audio processing — alternating left/right channel samples into a single interleaved buffer for I2S DMA transfer.

Key Insight: Create a gap of exactly n+1 nodes between two pointers. When the leading pointer reaches null, the trailing pointer is right before the node to delete. A sentinel node handles the edge case of deleting the head.

Thought Process:

1. Two-pass approach: count the length L, then delete the (L - n + 1)th node from the start. Simple but requires two traversals.
2. One-pass: advance second pointer n+1 steps ahead of first. Then move both at the same pace. When second reaches null, first is at the predecessor of the target.
3. A sentinel (dummy) node before head simplifies the case where n equals the list length (deleting the head itself) — first ends up at the sentinel, and first->next = first->next->next removes the original head.
4. Guard: if n exceeds the list length, second becomes null during the initial advance — return the original head unchanged.

Time Complexity: O(n) — single pass (the second pointer traverses the full list). Space Complexity: O(1) — two pointers and a sentinel.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode sentinel;
        sentinel.next = head;
        ListNode *first = &sentinel, *second = &sentinel;

        for (int i = 0; i <= n; i++) {
            if (!second) return head;
            second = second->next;
        }

        while (second) {
            first = first->next;
            second = second->next;
        }

        first->next = first->next->next;
        return sentinel.next;
    }
};

Embedded relevance: The two-pointer gap technique mirrors how ring buffer consumers track a "lag" behind the producer — maintaining a fixed offset to ensure a certain number of items remain buffered.

Key Insight: Partial reversal is the same as full reversal but with boundaries. Navigate to the node before left, reverse only the sublist from left to right, then reconnect both ends. A dummy node simplifies the case where left = 1.

Thought Process:

1. First, locate the node just before position left (call it pre). Also locate the node at position left (call it cur) and the node just after position right (call it target).
2. Reverse the sublist from cur to target using the standard three-pointer reversal, stopping when cur == target.
3. After reversal, pre->next points to the new sublist head (the old right node), and the old left node's next points to target (the node after the reversed section).
4. A dummy node before head handles left = 1 — otherwise pre would be null.

Time Complexity: O(n) — at most two passes (navigate to position + reverse sublist). Space Complexity: O(1) — constant number of pointers.

class Solution {
public:
    ListNode* reverseNode(ListNode* head, ListNode* target) {
        ListNode *pre = nullptr, *cur = head, *nxt;
        while (cur != target) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        head->next = target;
        return pre;
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy;
        dummy.next = head;
        if (!head) return head;

        ListNode *pre = &dummy, *cur = head, *target = head;
        while (--m) { pre = cur; cur = cur->next; }
        while (n--) { target = target->next; }

        pre->next = reverseNode(cur, target);
        return dummy.next;
    }
};

Embedded relevance: Partial list reversal is analogous to in-place byte reversal within a specific field of a protocol frame — reversing endianness of a multi-byte value without copying the entire frame.

Key Insight: In a circular list, you can always reach any node's predecessor by walking forward until you loop back around. Unlike the "delete node" trick for non-circular lists (copy-and-skip), here we can find the previous node and properly unlink the target.

Thought Process:

1. Copy-and-skip (like the standard "delete node" problem) works if the target is not the only node. But in a circular list we can do better — we can find the predecessor.
2. Start at the target node and walk forward through the circular list until runner->next == node. Now runner is the predecessor.
3. Set runner->next = node->next to unlink the target. If the target is the only node in the list (node->next == node), the list becomes empty.
4. Special case: if someone holds a "head" pointer to the deleted node, they need to update it. This problem only asks us to delete, not maintain a head reference.

Time Complexity: O(n) — worst case traverses the entire circular list to find the predecessor. Space Complexity: O(1) — one traversal pointer.

void deleteNode(ListNode* node) {
    if (!node) return;

    // Single node in circular list
    if (node->next == node) {
        delete node;
        return;
    }

    // Find predecessor by walking the circle
    ListNode* runner = node;
    while (runner->next != node) {
        runner = runner->next;
    }

    // Unlink and delete
    runner->next = node->next;
    delete node;
}

Embedded relevance: Circular linked lists are used in round-robin schedulers and timer wheel implementations. Deleting a node from a circular list mirrors cancelling a scheduled timer or removing a task from a round-robin rotation.

Key Insight: A sorted list already provides BST in-order traversal order. Instead of finding the middle element repeatedly (which is O(n) per level), simulate in-order traversal: advance a global list pointer as you build the tree bottom-up. The list pointer naturally visits nodes in sorted order.

Thought Process:

1. Array approach: copy to array, recursively pick the middle element as root — O(n) extra space for the array.
2. Find-middle approach: use slow/fast to find the middle of the list at each recursion level. But finding the middle is O(n) per call, giving O(n log n) total.
3. Optimal: count the list length first (O(n)). Then recurse with buildBST(start, end). At each leaf level, consume the current list node and advance the pointer. This simulates in-order traversal — left subtree consumes the first half of nodes, root consumes the middle, right subtree consumes the rest.
4. The recursion depth is O(log n) for a balanced tree, which is the space for the call stack.

Time Complexity: O(n) — each list node is visited exactly once during the in-order simulation. Space Complexity: O(log n) — recursion stack depth for a balanced tree.

class Solution {
    ListNode* cur;

    TreeNode* buildBST(int start, int end) {
        if (start > end) return nullptr;

        int mid = start + (end - start) / 2;

        TreeNode* left = buildBST(start, mid - 1);

        TreeNode* root = new TreeNode(cur->val);
        cur = cur->next;
        root->left = left;

        root->right = buildBST(mid + 1, end);

        return root;
    }

public:
    TreeNode* sortedListToBST(ListNode* head) {
        cur = head;
        int len = 0;
        ListNode* tmp = head;
        while (tmp) { len++; tmp = tmp->next; }
        return buildBST(0, len - 1);
    }
};

Embedded relevance: Building balanced search trees from sorted data is useful for constructing efficient lookup tables at boot time — for example, converting a sorted configuration key list into a BST for O(log n) runtime lookups instead of O(n) linear search.

Key Insight: For each node with a left child, find the rightmost node of the left subtree and thread it to the current node's right child. Then move the entire left subtree to the right side. This is a variant of Morris traversal — no stack or recursion needed.

Thought Process:

1. Recursive approach: flatten left, flatten right, attach left's tail to right subtree — O(n) time but O(h) stack space.
2. Stack-based iterative: pre-order traversal with a stack, re-linking as you go — O(n) time, O(h) space.
3. Morris-style O(1) space: for each node with a left child, find the left subtree's rightmost node (the in-order predecessor). Connect its right pointer to the current node's right child. Then move the left subtree to the right. This "threads" the tree without extra space.
4. After threading, set root->left = NULL and advance to root->right. Repeat until done.

Time Complexity: O(n) — each node is visited at most twice (once to find the predecessor, once to advance). Space Complexity: O(1) — no stack, no recursion, just pointer manipulation.

class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == NULL) return;
        while (root) {
            if (root->left) {
                TreeNode* pre = root->left;
                while (pre->right) pre = pre->right;
                pre->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            root = root->right;
        }
    }
};

Embedded relevance: Flattening a tree into a linked list is useful for serializing hierarchical device tree structures into a linear format for DMA transfer or flash storage — converting a tree representation into a sequential byte stream.