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

Practice

1. What does inserting a node at a specific middle position in a linked list mean?

easy

A. Adding a new node only at the start of the list

B. Adding a new node exactly at the given position counting from the head

C. Adding a new node only at the end of the list

D. Replacing the node at the given position with a new node

Solution

1. Step 1: Understand the position concept

   Inserting at a specific position means counting nodes from the head and placing the new node exactly there.

2. Step 2: Differentiate from other insertions

   Insertion at start or end is special cases; here we insert in the middle without removing nodes.

3. Final Answer:

   Adding a new node exactly at the given position counting from the head -> Option B

4. Quick Check:

   Insert at position = Insert node at that place [OK]

Hint: Insert at position means count nodes and place new node there [OK]

Common Mistakes:

• Confusing insertion with replacement
• Thinking insertion only happens at start or end
• Ignoring the position count from head

2. Which of the following C code snippets correctly inserts a new node at position 3 in a singly linked list?

easy

A. Traverse to node 2, set newNode->next = current->next; current->next = newNode;

B. Set newNode->next = head; head = newNode;

C. Traverse to node 3, set current->next = newNode; newNode->next = NULL;

D. Set newNode->next = NULL; current->next = newNode;

Solution

1. Step 1: Identify correct traversal

   To insert at position 3, we must reach node 2 (one before position 3).

2. Step 2: Link new node correctly

   Set newNode->next to current->next, then current->next to newNode to insert properly.

3. Final Answer:

   Traverse to node 2, set newNode->next = current->next; current->next = newNode; -> Option A

4. Quick Check:

   Insert at pos 3 = link after node 2 [OK]

Hint: Insert after (position-1)th node by adjusting pointers [OK]

Common Mistakes:

• Inserting at wrong node position
• Not updating newNode->next before linking
• Setting newNode->next to NULL incorrectly

3. What will be the linked list after inserting a node with value 99 at position 3 in the list 10 -> 20 -> 30 -> 40 -> NULL?

medium

A. 99 -> 10 -> 20 -> 30 -> 40 -> NULL

B. 10 -> 20 -> 30 -> 99 -> 40 -> NULL

C. 10 -> 20 -> 30 -> 40 -> 99 -> NULL

D. 10 -> 20 -> 99 -> 30 -> 40 -> NULL

Solution

1. Step 1: Identify position 3 in the list

   Positions: 1=10, 2=20, 3=30, so new node goes before 30.

2. Step 2: Insert new node at position 3

   New node with 99 points to 30, node 20 points to new node.

3. Final Answer:

   10 -> 20 -> 99 -> 30 -> 40 -> NULL -> Option D

4. Quick Check:

   Insert at pos 3 places 99 before 30 [OK]

Hint: Insert at pos 3 means new node is third in list [OK]

Common Mistakes:

• Inserting after instead of at position
• Appending at end instead of middle
• Confusing node values and positions

4. Given the following code snippet to insert at position 2, what is the error?

void insertAtPos(Node** head, int data, int pos) {
  Node* newNode = malloc(sizeof(Node));
  newNode->data = data;
  newNode->next = NULL;
  Node* temp = *head;
  for(int i = 1; i < pos - 1; i++) {
    temp = temp->next;
  }
  newNode->next = temp->next;
  temp->next = newNode;
}

medium

A. Memory for newNode is not allocated

B. newNode->next is not set before linking

C. Loop runs one time too many causing temp to be NULL

D. Head pointer is not updated after insertion

Solution

1. Step 1: Analyze loop for position 2

   Loop should run from i=1 to i < pos-1 to stop at node before insertion point.

2. Step 2: Check temp usage after loop

   Original loop runs one time too many, moving temp to node 2 instead of node 1, causing incorrect insertion or NULL access.

3. Final Answer:

   Loop runs one time too many causing temp to be NULL -> Option C

4. Quick Check:

   Loop overshoots node before position [OK]

Hint: Loop should stop at position-1 to avoid NULL [OK]

Common Mistakes:

• Loop runs to pos instead of pos-1
• Not checking for NULL before accessing temp->next
• Forgetting to allocate memory for new node

5. You have a singly linked list with 5 nodes: 1 -> 2 -> 3 -> 4 -> 5 -> NULL. You want to insert a node with value 99 at position 6. What should happen and what will be the final list?

hard

A. Node 99 is appended at the end; list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 99 -> NULL

B. Node 99 is inserted at position 5; list becomes 1 -> 2 -> 3 -> 4 -> 99 -> 5 -> NULL

C. Node 99 replaces node 5; list becomes 1 -> 2 -> 3 -> 4 -> 99 -> NULL

D. Insertion fails because position 6 is invalid; list remains unchanged

Solution

1. Step 1: Check list length and position

   List has 5 nodes; position 6 means insert after last node (append).

2. Step 2: Insert node at end

   Since position is one more than length, node 99 is added after node 5.

3. Final Answer:

   Node 99 is appended at the end; list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 99 -> NULL -> Option A

4. Quick Check:

   Insert at pos > length means append [OK]

Hint: Position beyond length means append at end [OK]

Common Mistakes:

• Rejecting valid append position
• Replacing last node instead of appending
• Inserting at wrong position due to off-by-one