Insert in a Sorted Linked List — Problem & Solution
Insert in a Sorted Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Insert in a Sorted Linked List is an easy coding problem on linked list, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Linked List
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list sorted in non-decreasing order and an integer data. Insert a new node holding data so that the list stays sorted, and return the head of the list.
Example 1
Input: head = [25,36,47,58,69,80], data = 19
Output: [19,25,36,47,58,69,80]
Explanation: 19 is smaller than everything, so the new node becomes the head.
Example 2
Input: head = [50,100], data = 75
Output: [50,75,100]
Example 3
Input: head = [1,3,3,7], data = 3
Output: [1,3,3,3,7]
Constraints
0 <= number of nodes <= 10^4-10^4 <= Node.val, data <= 10^4The list is sorted in non-decreasing order
Hints for Insert in a Sorted Linked List
Hint 1
The new node goes right before the first node whose value is larger than
data(or at the end).Hint 2
To insert there you need the node before that position — and the head has none.
Hint 3
Handle the new-head case first (empty list or
data< head's value); otherwise walk whilecur.nextexists andcur.next.val < data, then splice the node in aftercur.
How to solve Insert in a Sorted Linked List
Find the last node whose value is smaller than data and splice the new node in after it. If there is no such node, the new node becomes the head.
Approach
- Create the node
xholdingdata. - If the list is empty or
data <= head.val, setx.next = headand returnx. - Otherwise walk
curfromheadwhilecur.nextexists andcur.next.val < data. - Set
x.next = cur.next,cur.next = x, and returnhead.
Why it works
When the walk stops, every node up to cur holds a value below data, and cur.next (if any) holds a value at least data. Putting x between them keeps every adjacent pair in order, so the list stays sorted.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Inserting before the head changes the head — return the new node in that case.
- Check
cur.nextfor null before reading its value; the new node may belong at the tail. - An empty list becomes a single node.
Reference solution
Python
from typing import Optional
def sortedInsert(head: Optional[ListNode], data: int) -> Optional[ListNode]:
node = ListNode(data)
if head is None or data <= head.val:
node.next = head
return node
cur = head
while cur.next and cur.next.val < data:
cur = cur.next
node.next = cur.next
cur.next = node
return headJava
public static ListNode sortedInsert(ListNode head, int data) {
ListNode node = new ListNode(data);
if (head == null || data <= head.val) { node.next = head; return node; }
ListNode cur = head;
while (cur.next != null && cur.next.val < data) cur = cur.next;
node.next = cur.next;
cur.next = node;
return head;
}C++
ListNode* sortedInsert(ListNode* head, int data) {
ListNode* node = new ListNode(data);
if (!head || data <= head->val) { node->next = head; return node; }
ListNode* cur = head;
while (cur->next && cur->next->val < data) cur = cur->next;
node->next = cur->next;
cur->next = node;
return head;
}JavaScript
var sortedInsert = function(head, data) {
var node = new ListNode(data);
if (head === null || data <= head.val) { node.next = head; return node; }
var cur = head;
while (cur.next !== null && cur.next.val < data) cur = cur.next;
node.next = cur.next;
cur.next = node;
return head;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.