Sorted Insert In LinkedList - C++ Solution

1. Introduction

This blog post delves into a common problem in linked list manipulation: inserting a new node into a sorted linked list in its correct position. The challenge is to maintain the sorted order of the list after the insertion.

Problem

Given a sorted singly linked list in increasing order and a single node, the task is to insert the node into the list such that the list remains sorted.

Examples:

- Input: List = 2 —> 4 —> 6 —> 8 —> nullptr, Node = 9

Output: 2 —> 4 —> 6 —> 8 —> 9 —> nullptr

- Input: List = 2 —> 4 —> 6 —> 8 —> nullptr, Node = 1

Output: 1 —> 2 —> 4 —> 6 —> 8 —> nullptr

- Input: List = 1 —> 2 —> 4 —> 6 —> 8 —> 9 —> nullptr, Node = 5

Output: 1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> nullptr

2. Solution Steps

1. Define a ListNode structure for the linked list.

2. Create a function to insert a new node in the sorted list.

3. In the function, handle edge cases such as an empty list or insertion at the beginning.

4. Traverse the list to find the correct insertion point.

5. Insert the new node and update the pointers.

3. Code Program

#include <iostream>
using namespace std;

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

// Function to insert a new node in a sorted linked list
ListNode* sortedInsert(ListNode* head, ListNode* newNode) {
    if (head == nullptr || newNode->val <= head->val) {
        newNode->next = head;
        return newNode;
    }

    ListNode* current = head;
    while (current->next != nullptr && current->next->val < newNode->val) {
        current = current->next;
    }

    newNode->next = current->next;
    current->next = newNode;
    return head;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " —> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a sorted linked list
    ListNode* head = new ListNode(2);
    head->next = new ListNode(4);
    head->next->next = new ListNode(6);
    head->next->next->next = new ListNode(8);

    // Inserting a new node
    ListNode* newNode = new ListNode(5);
    head = sortedInsert(head, newNode);

    printLinkedList(head);
    return 0;
}

Output:

2 —> 4 —> 5 —> 6 —> 8 —> nullptr

Explanation:

The sortedInsert function inserts a new node into a sorted linked list while maintaining the list's sorted order. It first checks if the new node should be inserted at the beginning of the list. If not, it traverses the list to find the correct insertion point, updates the pointers accordingly, and returns the head of the modified list. The main function demonstrates this by creating a sorted list, inserting a new node, and then printing the updated list.