Merge In Between Linked Lists - Practice Coding Problems

Merge In Between Linked Lists - Problem

Linked List Medium

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the ath node to the bth node, and put list2 in their place.

Build the result list and return its head.

Input & Output

Example 1 — Basic Replacement

$ Input: list1 = [0,1,2,3,4], a = 1, b = 3, list2 = [1000000,1000001,1000002]

› Output: [0,1000000,1000001,1000002,4]

💡 Note: Remove nodes from index 1 to 3 (values 1,2,3) and replace with list2. Keep node 0 and node 4, insert list2 in between.

Example 2 — Single Node Replacement

$ Input: list1 = [0,1,2,3,4], a = 3, b = 3, list2 = [1000000,1000001]

› Output: [0,1,2,1000000,1000001,4]

💡 Note: Remove only the node at index 3 (value 3) and replace with list2. Result keeps 0,1,2, inserts list2, then keeps 4.

Example 3 — Edge Case at End

$ Input: list1 = [0,1,2], a = 1, b = 2, list2 = [5,6,7]

› Output: [0,5,6,7]

💡 Note: Remove nodes 1 and 2 from the end, replace with list2. Only node 0 remains from original list.

Constraints

3 ≤ list1.length ≤ 10⁴
1 ≤ a ≤ b < list1.length - 1
1 ≤ list2.length ≤ 10⁴
1 ≤ list1[i], list2[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Lists

list1=[0,1,2,3,4], a=1, b=3, list2=[A,B,C]

Identify Segment

Remove nodes from index a to b (inclusive)

Insert Replacement

Splice list2 into the gap where removed nodes were

Key Takeaway

🎯 Key Insight: Use direct pointer manipulation to reconnect the list segments without extra space

Asked in

M Microsoft 35 a Amazon 28 G Google 22

The key insight is to use direct pointer manipulation to splice list2 into list1 by identifying connection points and reconnecting pointers. The optimal approach uses O(1) space by manipulating pointers directly without extra arrays. Time: O(n+m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Direct Pointer Manipulation	O(n + m)	O(1)	Directly manipulate pointers to splice list2 into list1 without extra space
Brute Force - Array Conversion	O(n + m)	O(n + m)	Convert linked lists to arrays, manipulate arrays, then rebuild linked list

Direct Pointer Manipulation — Algorithm Steps

Step 1: Find node before position a
Step 2: Find node at position b
Step 3: Connect pre-a node to list2 head
Step 4: Connect list2 tail to post-b node

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Positions

Find nodes before a and after b

Find List2 Tail

Traverse to end of list2

Reconnect Pointers

Link prev_a → list2_head, list2_tail → post_b

Code -

solution.c — C

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

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

struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = createNode(arr[0]);
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createNode(arr[i]);
        current = current->next;
    }
    return head;
}

int listToArray(struct ListNode* head, int* arr) {
    int size = 0;
    struct ListNode* current = head;
    while (current) {
        arr[size++] = current->val;
        current = current->next;
    }
    return size;
}

struct ListNode* solution(struct ListNode* list1, int a, int b, struct ListNode* list2) {
    // Find the node before position a
    struct ListNode* prevA = list1;
    for (int i = 0; i < a - 1; i++) {
        prevA = prevA->next;
    }
    
    // Find the node after position b
    struct ListNode* nodeB = prevA;
    for (int i = 0; i < b - a + 2; i++) {
        nodeB = nodeB->next;
    }
    
    // Find the tail of list2
    struct ListNode* list2Tail = list2;
    while (list2Tail->next) {
        list2Tail = list2Tail->next;
    }
    
    // Connect prevA to list2 head
    prevA->next = list2;
    
    // Connect list2 tail to node after b
    list2Tail->next = nodeB;
    
    return list1;
}

int main() {
    char line[10000];
    int list1Vals[1000], list2Vals[1000];
    int size1 = 0, size2 = 0;
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token) {
        if (strlen(token) > 0 && token[0] != '\n') {
            list1Vals[size1++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int a, b;
    scanf("%d", &a);
    scanf("%d", &b);
    
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token) {
        if (strlen(token) > 0 && token[0] != '\n') {
            list2Vals[size2++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    struct ListNode* list1 = arrayToList(list1Vals, size1);
    struct ListNode* list2 = arrayToList(list2Vals, size2);
    
    struct ListNode* result = solution(list1, a, b, list2);
    
    int output[2000];
    int outputSize = listToArray(result, output);
    
    printf("[");
    for (int i = 0; i < outputSize; i++) {
        printf("%d", output[i]);
        if (i < outputSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

One pass to find positions in list1, one pass to find tail of list2

✓ Linear Growth

Space Complexity

O(1)

Only using a few pointer variables, no extra data structures

✓ Linear Space

32.5K Views

Medium Frequency

~15 min Avg. Time

892 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

Direct Pointer Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler