Insert at Middle Specific Position in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting at middle position in linked list

What is the printed linked list after inserting a node with value 99 at position 3?

DSA C

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

struct Node {
    int data;
    struct Node* next;
};

void insertAtPosition(struct Node** head, int data, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        free(newNode);
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("null\n");
}

int main() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->next->data = 4;
    head->next->next->next->next = NULL;

    insertAtPosition(&head, 99, 3);
    printList(head);
    return 0;
}

A 1 -> 2 -> 99 -> 3 -> 4 -> null

B 1 -> 2 -> 3 -> 99 -> 4 -> null

C 1 -> 99 -> 2 -> 3 -> 4 -> null

D 99 -> 1 -> 2 -> 3 -> 4 -> null

💡 Hint

Remember that position 3 means the new node should be the third node in the list.

The function inserts the new node at position 3, so after nodes with values 1 and 2. The new node with value 99 comes before the original node with value 3.

❓ Predict Output

intermediate

Result of inserting at position beyond list length

What is the output after trying to insert value 50 at position 10 in the list 10 -> 20 -> 30 -> null?

DSA C

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

struct Node {
    int data;
    struct Node* next;
};

void insertAtPosition(struct Node** head, int data, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        free(newNode);
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("null\n");
}

int main() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 10;
    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 20;
    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;

    insertAtPosition(&head, 50, 10);
    printList(head);
    return 0;
}

A 10 -> 50 -> 20 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 10 -> 20 -> 30 -> 50 -> null

D 50 -> 10 -> 20 -> 30 -> null

💡 Hint

If the position is beyond the list length, the insertion does not happen.

The function checks if the position is valid. Since position 10 is beyond the list length, the new node is not inserted and the list remains unchanged.

🔧 Debug

advanced

Identify the bug in insert at middle position function

What is the bug in this insertAtPosition function that causes a crash when inserting at position 3 in an empty list?

DSA C

void insertAtPosition(struct Node** head, int data, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; i < position - 1; i++) {
        temp = temp->next;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

A The loop does not check if temp is NULL before accessing temp->next, causing a crash.

B The newNode is not allocated memory before use.

C The function does not update the head pointer when position is 1.

D The function frees newNode before inserting it.

💡 Hint

Think about what happens when the list is empty and position is 3.

When the list is empty (*head is NULL), temp is NULL. The loop tries to access temp->next without checking if temp is NULL, causing a crash.

🧠 Conceptual

advanced

Time complexity of inserting at middle position in singly linked list

What is the time complexity of inserting a node at a specific middle position in a singly linked list of size n?

A O(1) because insertion is always at the head.

B O(log n) because of binary search to find the position.

C O(n) because you must traverse the list to the position before insertion.

D O(n^2) because each insertion requires traversing the entire list.

💡 Hint

Think about how you find the position to insert in a singly linked list.

To insert at a specific position, you must traverse the list up to that position, which takes O(n) time. The insertion itself is O(1).

🚀 Application

expert

Result of multiple insertions at various middle positions

Given an initially empty singly linked list, after performing these insertions in order: 1) Insert 10 at position 1 2) Insert 20 at position 2 3) Insert 15 at position 2 4) Insert 5 at position 1 5) Insert 25 at position 5 What is the final printed linked list?

DSA C

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

struct Node {
    int data;
    struct Node* next;
};

void insertAtPosition(struct Node** head, int data, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        free(newNode);
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("null\n");
}

int main() {
    struct Node* head = NULL;
    insertAtPosition(&head, 10, 1);
    insertAtPosition(&head, 20, 2);
    insertAtPosition(&head, 15, 2);
    insertAtPosition(&head, 5, 1);
    insertAtPosition(&head, 25, 5);
    printList(head);
    return 0;
}

A 5 -> 15 -> 10 -> 20 -> 25 -> null

B 10 -> 5 -> 15 -> 20 -> 25 -> null

C 5 -> 10 -> 20 -> 15 -> 25 -> null

D 5 -> 10 -> 15 -> 20 -> 25 -> null

💡 Hint

Insertions shift existing nodes to the right from the insertion position.

Step by step: - Insert 10 at pos 1: 10 - Insert 20 at pos 2: 10 -> 20 - Insert 15 at pos 2: 10 -> 15 -> 20 - Insert 5 at pos 1: 5 -> 10 -> 15 -> 20 - Insert 25 at pos 5: 5 -> 10 -> 15 -> 20 -> 25