Insert into a Sorted Circular Linked List

Insert into a Sorted Circular Linked List - Problem

Linked List Medium

Given a Circular Linked List node, which is sorted in non-descending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list.

The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.

If the list is empty (i.e., the given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.

Input & Output

Example 1 — Normal Insertion

$ Input: head = [1,3,4], insertVal = 2

› Output: [1,2,3,4]

💡 Note: Insert 2 between 1 and 3 to maintain sorted order. The circular structure is preserved with the last node pointing back to the first.

Example 2 — Empty List

$ Input: head = [], insertVal = 1

› Output: [1]

💡 Note: Empty list case: Create a new single-node circular list where the node points to itself.

Example 3 — Insert at Boundary

$ Input: head = [3,4,1], insertVal = 2

› Output: [3,4,1,2]

💡 Note: Insert 2 at the wrap-around point between 4 and 1, since 2 fits between the maximum (4) and minimum (1) values.

Constraints

0 ≤ Number of Nodes ≤ 5 × 10⁴
-10⁶ ≤ Node.val ≤ 10⁶
-10⁶ ≤ insertVal ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Circular linked list [1,3,4] and insertVal = 2

Process

Find correct position between 1 and 3

Output

Resulting circular list [1,2,3,4]

Key Takeaway

🎯 Key Insight: In a sorted circular list, there's exactly one transition point from maximum to minimum value where boundary insertions occur

Asked in

F Facebook 25 G Google 20 a Amazon 15 M Microsoft 12

The key insight is recognizing the three insertion cases in a circular sorted list: normal insertion between nodes, insertion at the wrap-around point, and handling uniform values. The optimal approach uses two pointers to traverse the list once, checking all conditions simultaneously. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Traversal	O(n)	O(1)	Traverse the circular list once to find the correct insertion position
Two-Pointer Approach	O(n)	O(1)	Use two pointers to efficiently find insertion position while handling edge cases

Single Pass Traversal — Algorithm Steps

Step 1: Handle empty list by creating new single-node circular list
Step 2: Traverse the list looking for correct insertion point
Step 3: Check three cases: between two nodes, at wrap-around, or all same values
Step 4: Insert new node and maintain circular structure

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin traversal from given head node

Check Cases

Check normal insertion, wrap-around, or same values

Insert

Insert new node and maintain circular structure

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head, int insertVal) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = insertVal;
    newNode->next = NULL;
    
    // Case 1: Empty list
    if (!head) {
        newNode->next = newNode;
        return newNode;
    }
    
    // Case 2: Single node
    if (head->next == head) {
        head->next = newNode;
        newNode->next = head;
        return head;
    }
    
    struct ListNode* prev = head;
    struct ListNode* curr = head->next;
    
    while (1) {
        // Case 3: Normal insertion
        if (prev->val <= insertVal && insertVal <= curr->val) {
            break;
        }
        
        // Case 4: Wrap-around point
        if (prev->val > curr->val) {
            if (insertVal >= prev->val || insertVal <= curr->val) {
                break;
            }
        }
        
        prev = curr;
        curr = curr->next;
        
        // Case 5: Full circle
        if (prev == head) {
            break;
        }
    }
    
    prev->next = newNode;
    newNode->next = curr;
    return head;
}

struct ListNode* arrayToCircularList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    struct ListNode* curr = head;
    for (int i = 1; i < size; i++) {
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->val = arr[i];
        curr = curr->next;
    }
    curr->next = head;
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int headArray[100];
    int size = 0;
    if (strncmp(line, "[]", 2) != 0) {
        char* ptr = line + 1; // Skip '['
        char* token = strtok(ptr, ",]");
        while (token != NULL) {
            headArray[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int insertVal;
    scanf("%d", &insertVal);
    
    struct ListNode* head = arrayToCircularList(headArray, size);
    struct ListNode* resultHead = solution(head, insertVal);
    
    // Convert back to array and print
    printf("[");
    if (resultHead) {
        printf("%d", resultHead->val);
        struct ListNode* curr = resultHead->next;
        while (curr != resultHead) {
            printf(",%d", curr->val);
            curr = curr->next;
        }
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal through the circular list, visiting each node once

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for pointers and new node

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler