Linked List Interview Problems for Embedded Engineers

Linked lists are fundamental in embedded systems — RTOS task queues, memory pool free lists, interrupt handler chains, and message queues all use linked list structures internally. Mastering in-place linked list manipulation with O(1) space is essential when working without dynamic memory.

Problems

#	Problem	Difficulty	Frequency
1	Reverse Linked List	Easy	★★★★★
2	Linked List Cycle	Easy	★★★★★
3	Delete Node in a Linked List	Easy	★★★★★
4	Remove Duplicates from Sorted List	Easy	★★★★★
5	Merge Two Sorted Lists	Easy	★★★★★
6	Palindrome Linked List	Easy	★★★★★
7	Remove Linked List Elements	Easy	★★★★★
8	Intersection of Two Linked Lists	Easy	★★★★★
9	Middle of linked list	Easy	★★★★★
10	Implement queue by linked list	Easy	★★★★★
11	Reorder List	Medium	★★★★★
12	Delete nth node from end of linked list	Medium	★★★★★
13	Reverse Linked List II	Medium	★★★★★
14	Delete node in circular linked list (given only pointer to node)	Medium	★★★★★
15	Convert singly linked list to BST	Medium	★★★★★
16	Flatten Binary Tree to Linked List	Medium	★★★★★

Pattern Cheat Sheet

Pattern	Technique	Problems
Pointer reversal	Iterate with prev/curr/next	Reverse List, Reverse List II, Palindrome
Slow/fast pointers	Detect cycles, find middle	Cycle Detection, Palindrome, Reorder
Dummy head node	Simplify edge cases for head changes	Merge, Remove Elements, Remove Duplicates, Delete Nth
Two-pointer gap	Advance one pointer ahead, walk both	Delete Nth from End, Intersection
Composite	Combine multiple patterns	Reorder (find middle + reverse + merge)

Implementation

Reverse Linked List Easy ★★★★★

Problem: Given the head of a singly linked list, reverse the list and return the reversed list.

QSolution — O(n) time, O(1) space — Iterative Pointer Reversal

Approach: Walk through the list with three pointers: pre, cur, and nxt. At each node, save the next pointer, reverse the current node's link to point backward, then advance all three pointers forward. After the loop, pre points to the new head.

cpp

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.

Linked List Cycle Easy ★★★★★

Problem: Given the head of a linked list, determine if the linked list has a cycle in it.

QSolution — O(n) time, O(1) space — Floyd's Cycle Detection (Slow/Fast Pointers)

Approach: Use two pointers moving at different speeds — slow advances one step, fast advances two steps. If there's a cycle, fast will eventually lap slow and they'll meet. If fast reaches null, there's no cycle. This is Floyd's tortoise-and-hare algorithm.

cpp

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.

Delete Node in a Linked List Easy ★★★★★

Problem: Given only access to a node in a singly linked list (not the tail), delete that node.

QSolution — O(1) time, O(1) space — Copy-and-Skip

Approach: Since you can't access the previous node, copy the value of the next node into the current node, then skip over the next node. This effectively "becomes" the next node and deletes it. A clever trick, but be aware: this changes the node identity, which matters if external pointers reference the deleted node.

cpp

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;
    }
};

Remove Duplicates from Sorted List Easy ★★★★★

Problem: Given the head of a sorted linked list, delete all duplicates such that each element appears only once.

QSolution — O(n) time, O(1) space — Single Pass

Approach: Walk through the sorted list comparing each node with the next. When duplicates are found, skip the duplicate node by updating the next pointer. Since the list is sorted, all duplicates are adjacent.

cpp

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;
    }
};

Merge Two Sorted Lists Easy ★★★★★

Problem: Given the heads of two sorted linked lists, merge them into one sorted linked list.

QSolution — O(n+m) time, O(1) space — Dummy Head + Compare

Approach: Create a dummy head node to simplify logic (avoids special-casing the first node). Compare the heads of both lists, append the smaller one to the result, and advance that list's pointer. When one list is exhausted, append the remainder of the other.

cpp

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's stable, O(n log n), and requires no random access.

Reorder List Medium ★★★★★

Problem: Given a singly linked list L0→L1→...→Ln, reorder it to L0→Ln→L1→Ln-1→... in-place.

QSolution — O(n) time, O(1) space — Find Middle + Reverse + Merge

Approach: This is a composite problem combining three linked list techniques: (1) Find the middle using slow/fast pointers, (2) Reverse the second half, (3) Interleave-merge the two halves. Each step is O(n) time and O(1) space.

cpp

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;
        }
    }
};

Palindrome Linked List Easy ★★★★★

Problem: Given the head of a singly linked list, return true if it is a palindrome.

QSolution — O(n) time, O(1) space — Reverse Second Half + Compare

Approach: Find the middle with slow/fast pointers, reverse the second half in-place, then compare both halves node by node. If all values match, it's a palindrome. This avoids copying the list to an array (which would use O(n) space).

cpp

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;
    }
};

Remove Linked List Elements Easy ★★★★★

Problem: Given the head of a linked list and an integer val, remove all nodes with that value.

QSolution — O(n) time, O(1) space — Dummy Head

Approach: Use a dummy node before the head to handle the case where the head itself needs to be removed. Walk through the list, skipping nodes whose value matches. The dummy node eliminates the need for special-case logic.

cpp

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;
    }
};

Intersection of Two Linked Lists Easy ★★★★★

Problem: Given the heads of two singly linked lists, return the node at which they intersect, or null.

QSolution — O(N) time, O(1) space — Length Difference

Approach: Count the lengths of both lists. Advance the longer list by the length difference so both pointers are equidistant from the potential intersection. Then walk both forward simultaneously — the first node where they meet is the intersection.

cpp

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;
    }
};

Delete Nth Node From End of Linked List Medium ★★★★★

Problem: Given the head of a linked list, remove the nth node from the end and return its head.

QSolution — O(L) time, O(1) space — Two-Pointer Gap

Approach: Advance the first pointer n+1 steps ahead, creating a gap. Then move both pointers forward until the first reaches the end. The second pointer is now right before the node to delete. Use a sentinel node to handle edge cases (e.g., deleting the head).

cpp

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;
    }
};

Reverse Linked List II Medium ★★★★★

Problem: Given the head of a singly linked list and two integers left and right, reverse the nodes from position left to position right.

QSolution — O(n) time, O(1) space — Partial Reversal with Dummy

Approach: Navigate to the node just before position left. Reverse only the sublist from left to right using the standard reversal technique. Reconnect the reversed portion to the rest of the list. A dummy node simplifies handling the case where left = 1 (reversing from the head).

cpp

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;
    }
};

Flatten Binary Tree to Linked List Medium ★★★★★

Problem: Given the root of a binary tree, flatten the tree into a linked list in-place following pre-order traversal.

QSolution — O(n) time, O(1) space — Morris Traversal Variant

Approach: For each node with a left child, find the rightmost node of the left subtree (its in-order predecessor). Connect that node's right pointer to the current node's right child, then move the entire left subtree to the right side. This threading approach uses O(1) extra space — no recursion stack needed.

cpp

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;
        }
    }
};