Merge In Between Linked Lists - LeetCode Daily Challenge

Problem Statement

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.

The blue edges and nodes in the following figure indicate the result:

Example 1

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Try here before watching the video.

Video Explanation

Java Code

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode start = null, end = list1;

        for(int i = 0; i <= b; i++) {
            if(i == a - 1) {
                start = end;
            }
            end = end.next;
        }

        start.next = list2;

        while(list2.next != null) {
            list2 = list2.next;
        }

        list2.next = end;
        return list1;
    }
}

C++ Code

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode* start = NULL;
        ListNode* end = list1;

        for(int i = 0; i <= b; i++) {
            if(i == a - 1) {
                start = end;
            }
            end = end->next;
        }

        start->next = list2;

        while(list2->next != NULL) {
            list2 = list2->next;
        }

        list2->next = end;
        return list1;
    }
};

Python Code

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        start = None
        end = list1

        for i in range(b + 1):
            if i == a - 1:
                start = end
            end = end.next

        start.next = list2

        while list2.next is not None:
            list2 = list2.next

        list2.next = end
        return list1

Javascript Code

var mergeInBetween = function(list1, a, b, list2) {
    let start = null;
    let end = list1;

    for(let i = 0; i <= b; i++) {
        if(i === a - 1) {
            start = end;
        }
        end = end.next;
    }

    start.next = list2;

    while(list2.next !== null) {
        list2 = list2.next;
    }

    list2.next = end;
    return list1;
};

Go Code

func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
    start := &ListNode{}
    end := list1

    for i := 0; i <= b; i++ {
        if i == a - 1 {
            start = end
        }
        end = end.Next
    }

    start.Next = list2

    for list2.Next != nil {
        list2 = list2.Next
    }

    list2.Next = end
    return list1
}

Complexity Analysis

Time Complexity: O(M + N), where M is the length of list1 and N is the length of list2.
Space Complexity: O(1), we are not using any extra space.