Insert into a Sorted Circular Linked List - CPP Solution

1. Introduction

This blog post discusses the implementation of inserting a new node into a sorted circular linked list. The challenge involves correctly placing the new node while maintaining the circular and sorted nature of the list.

Problem

Given a node head that is a reference to a node in a sorted circular linked list, write a function to insert a new value into the list. The list is sorted in non-decreasing order. The function should return the reference to the head of the list.

2. Solution Steps

1. Create a new node with the given value.

2. If the list is empty, make the new node a circular list and return it as the head.

3. If the list is not empty, locate the correct position for the new node.

4. Insert the new node into the list while maintaining the sorted order.

5. Handle edge cases such as inserting before the head or at the end of the list.

6. Return the head of the list.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to insert a new node in a sorted circular linked list
ListNode* insertIntoSortedCircularList(ListNode* head, int insertVal) {
    ListNode* newNode = new ListNode(insertVal);
    if (!head) {
        newNode->next = newNode;
        return newNode;
    }

    ListNode *curr = head, *next = head->next;
    while (next != head) {
        if (curr->val <= insertVal && insertVal <= next->val) break;
        if (curr->val > next->val && (insertVal > curr->val || insertVal < next->val)) break;
        curr = next;
        next = next->next;
    }
    curr->next = newNode;
    newNode->next = next;
    return head;
}

// Function to print the circular linked list
void printCircularList(ListNode* head) {
    if (!head) return;
    ListNode *start = head;
    do {
        cout << head->val << " -> ";
        head = head->next;
    } while (head != start);
    cout << "Back to start (" << head->val << ")" << endl;
}

int main() {
    // Creating a circular linked list: 3 -> 4 -> 1
    ListNode* head = new ListNode(3);
    head->next = new ListNode(4);
    head->next->next = new ListNode(1);
    head->next->next->next = head; // Making it circular

    head = insertIntoSortedCircularList(head, 2);
    printCircularList(head); // Expected output: 3 -> 4 -> 1 -> 2 -> Back to start (3)
    return 0;
}

Output:

3 -> 4 -> 1 -> 2 -> Back to start (3)

Explanation:

The insertIntoSortedCircularList function handles the insertion of a new value into a sorted circular linked list. It first handles the case where the list is empty by creating a circular list with the new node. If the list is not empty, it locates the position where the new node fits while maintaining the sorted order, including the cases where the new value is the smallest or largest in the list. The function then inserts the new node and returns the head of the list, ensuring the list remains circular and sorted.