Insert Ingredients in Sorted Order — Problem Statement & Solution Guide

Linked ListMediumMixed

TimeO(N+M)

SpaceO(1)

Problem Description

You are provided with the head pointer of a singly linked list containing integer values arranged in non-decreasing order. Additionally, you are given an array of integers representing new elements that must be integrated into the list. Your objective is to insert each element from the array into the linked list such that the final sequence of nodes remains strictly sorted in non-decreasing order.

The insertion process must maintain the integrity of the linked list structure. For each value in the input array, determine the correct position within the existing list where the new node should be placed to preserve the sorted invariant. If multiple positions are valid (i.e., the new value is equal to existing values), the new node may be inserted at any position among the equal values, provided the overall order remains non-decreasing.

Return the head pointer of the modified linked list after all insertions have been completed. The solution should handle edge cases such as an empty initial list or an empty array of new elements efficiently.

DSA Pattern Breakdown

"Insert Ingredients in Sorted Order"

medium

WHY DOES IT MATTER?

Merging sorted sequences is a fundamental pattern that appears in many domains—database index maintenance, streaming data aggregation, and real‑time event ordering. Mastering it enables engineers to keep data structures consistent with minimal overhead.

OPTIMIZATION CHALLENGE

The key insight is to avoid resetting the traversal pointer after each insertion. By maintaining a single moving cursor in the original list and advancing it only forward, each node is examined once, collapsing the quadratic scan into a linear merge.

REAL-WORLD CONNECTION

Think of a live news feed where headlines (already sorted by timestamp) must be interleaved with breaking news alerts arriving in order. The system merges the two streams on the fly so the final timeline remains chronologically correct without re‑sorting the entire feed.

During an interview, write a helper that inserts a single value given a start node; then extend it to a loop that walks both the list and the array. Keep the code modular and comment the invariant: "All nodes before 'prev' are already merged and sorted."

COMPLEXITY AT A GLANCE

⏱ Time:O(N+M)

💾 Space:O(1)

Core Theory — Why This Approach?

When a singly linked list is already sorted, inserting a new element while preserving order can be performed by a single linear scan that finds the correct predecessor node. The naive method would restart the scan for each new element, leading to quadratic time on large inputs because each insertion may traverse the entire list. The optimal paradigm treats the existing list and the array of new values as two sorted streams and merges them in-place, similar to the merge step of merge‑sort. By advancing pointers only forward and creating new nodes on the fly, we guarantee that each original node and each new element is visited exactly once, achieving linear time overall while using only constant auxiliary space.

Interview Questions on This Problem

Q1How would you insert multiple values into a sorted singly linked list in O(N+M) time, where N is the list length and M is the number of new values?

Iterate through both the list and the sorted array simultaneously, using two pointers. At each step, compare the current list node's value with the next array element; insert the smaller one by adjusting next pointers, advancing the corresponding pointer, and continue until both sources are exhausted.

Q2Why is it inefficient to insert each new element by traversing the list from the head each time?

Because each traversal may scan up to O(N) nodes, and doing this for M elements results in O(N·M) time, which becomes prohibitive for large N and M. The repeated scans duplicate work that could be avoided by a single pass merge.

Q3Can you modify the algorithm to work with a doubly linked list without changing its asymptotic complexity?

Yes. The same two‑pointer merge logic applies; the only difference is that when inserting a node you also update the previous pointer of the successor, but the number of pointer updates remains O(N+M), preserving O(N+M) time and O(1) extra space.

Examples

Example 1

Input

head = [1, 3, 5, 7], newValues = [2, 4, 6]

Output

[1, 2, 3, 4, 5, 6, 7]

Explanation: Start with list 1->3->5->7. Insert 2: 2 is between 1 and 3, so list becomes 1->2->3->5->7. Insert 4: 4 is between 3 and 5, so list becomes 1->2->3->4->5->7. Insert 6: 6 is between 5 and 7, so list becomes 1->2->3->4->5->6->7. Final list is 1->2->3->4->5->6->7.

Example 2

Input

head = [10, 20, 30], newValues = [5, 15, 25, 35]

Output

[5, 10, 15, 20, 25, 30, 35]

Explanation: Start with list 10->20->30. Insert 5: 5 is less than 10, so it becomes the new head: 5->10->20->30. Insert 15: 15 is between 10 and 20, so list becomes 5->10->15->20->30. Insert 25: 25 is between 20 and 30, so list becomes 5->10->15->20->25->30. Insert 35: 35 is greater than 30, so it is appended at the end: 5->10->15->20->25->30->35.

Example 3

Input

head = [], newValues = [4, 2, 6, 1, 3, 5]

Output

[1, 2, 3, 4, 5, 6]

Explanation: Start with an empty list. Insert 4: list becomes 4. Insert 2: 2 is less than 4, so list becomes 2->4. Insert 6: 6 is greater than 4, so list becomes 2->4->6. Insert 1: 1 is less than 2, so list becomes 1->2->4->6. Insert 3: 3 is between 2 and 4, so list becomes 1->2->3->4->6. Insert 5: 5 is between 4 and 6, so list becomes 1->2->3->4->5->6.

Example 4

Input

head = [1, 1, 1], newValues = [1, 1]

Output

[1, 1, 1, 1, 1]

Explanation: Start with list 1->1->1. Insert 1: Since all values are equal, the new node can be inserted anywhere among the 1s. Let's insert it at the end: 1->1->1->1. Insert another 1: Again, insert at the end: 1->1->1->1->1. The final list contains five 1s in non-decreasing order.

Constraints

0 <= length of initial linked list <= 10^5
0 <= length of newValues array <= 10^5
-10^9 <= value of any node or array element <= 10^9
The initial linked list is guaranteed to be sorted in non-decreasing order
Time complexity should be O(N + M log M) or better, where N is the length of the initial list and M is the length of the newValues array

Optimal Approach & Strategy

Use two pointers—one for the current node in the list and one for the next value in the array—and merge them in a single linear scan, inserting nodes as you go.

Brute Force Approach

For each new element, start at the head of the list and walk forward until you find the correct insertion point, then splice the node in. Repeat this for every element.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N+M)

function insertIngredients(head, ingredients) {
   let dummy = new ListNode(0);
   let current = dummy;
   let ingredientIndex = 0;
   while (head !== null) {
       while (ingredientIndex < ingredients.length && ingredients[ingredientIndex] <= head.val) {
           current.next = new ListNode(ingredients[ingredientIndex]);
           current = current.next;
           ingredientIndex++;
       }
       current.next = head;
       current = current.next;
       head = head.next;
   }
   while (ingredientIndex < ingredients.length) {
       current.next = new ListNode(ingredients[ingredientIndex]);
       current = current.next;
       ingredientIndex++;
   }
   return dummy.next;
}

class Solution {
public:
   ListNode* insertIngredients(ListNode* head, vector<int>& ingredients) {
       ListNode dummy(0);
       ListNode* current = &dummy;
       int ingredientIndex = 0;
       while (head) {
           while (ingredientIndex < ingredients.size() && ingredients[ingredientIndex] <= head->val) {
               current->next = new ListNode(ingredients[ingredientIndex]);
               current = current->next;
               ingredientIndex++;
           }
           current->next = head;
           current = current->next;
           head = head->next;
       }
       while (ingredientIndex < ingredients.size()) {
           current->next = new ListNode(ingredients[ingredientIndex]);
           current = current->next;
           ingredientIndex++;
       }
       return dummy.next;
   }
};

class Solution {
   public ListNode insertIngredients(ListNode head, int[] ingredients) {
       ListNode dummy = new ListNode(0);
       ListNode current = dummy;
       int ingredientIndex = 0;
       while (head != null) {
           while (ingredientIndex < ingredients.length && ingredients[ingredientIndex] <= head.val) {
               current.next = new ListNode(ingredients[ingredientIndex]);
               current = current.next;
               ingredientIndex++;
           }
           current.next = head;
           current = current.next;
           head = head.next;
       }
       while (ingredientIndex < ingredients.length) {
           current.next = new ListNode(ingredients[ingredientIndex]);
           current = current.next;
           ingredientIndex++;
       }
       return dummy.next;
   }
}

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

def insertIngredients(head, ingredients):
   dummy = ListNode(0)
   current = dummy
   ingredient_index = 0
   while head:
       while ingredient_index < len(ingredients) and ingredients[ingredient_index] <= head.val:
           current.next = ListNode(ingredients[ingredient_index])
           current = current.next
           ingredient_index += 1
       current.next = head
       current = current.next
       head = head.next
   while ingredient_index < len(ingredients):
       current.next = ListNode(ingredients[ingredient_index])
       current = current.next
       ingredient_index += 1
   return dummy.next

function insertIngredients(head, ingredients) {
   let dummy = new ListNode(0);
   let current = dummy;
   let ingredientIndex = 0;
   while (head !== null) {
       while (ingredientIndex < ingredients.length && ingredients[ingredientIndex] <= head.val) {
           current.next = new ListNode(ingredients[ingredientIndex]);
           current = current.next;
           ingredientIndex++;
       }
       current.next = head;
       current = current.next;
       head = head.next;
   }
   while (ingredientIndex < ingredients.length) {
       current.next = new ListNode(ingredients[ingredientIndex]);
       current = current.next;
       ingredientIndex++;
   }
   return dummy.next;
}

Asked in Top Tech Interviews

linked-listsmediumiterative-approach

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Insert Ingredients in Sorted Order Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Insert Ingredients in Sorted Order — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor