Insert in a Sorted Linked List

Easy
1998.

Insert in a Sorted Linked List

EasyLinked ListAmazonMicrosoft

Insert in a Sorted Linked List is an easy coding problem on linked list, asked in Amazon and Microsoft interviews.

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^4
  • The list is sorted in non-decreasing order
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} data
 * @return {ListNode}
 */
var sortedInsert = function(head, data) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • The list is sorted in non-decreasing order

Hints for Insert in a Sorted Linked List

  1. Hint 1

    The new node goes right before the first node whose value is larger than data (or at the end).

  2. Hint 2

    To insert there you need the node before that position — and the head has none.

  3. Hint 3

    Handle the new-head case first (empty list or data < head's value); otherwise walk while cur.next exists and cur.next.val < data, then splice the node in after cur.

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

  1. Create the node x holding data.
  2. If the list is empty or data <= head.val, set x.next = head and return x.
  3. Otherwise walk cur from head while cur.next exists and cur.next.val < data.
  4. Set x.next = cur.next, cur.next = x, and return head.

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.next for 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 head

Java

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.