Merge In Between Linked Lists - Leetcode Solution

Problem Statement:

Given two linked lists, list1 and list2, where list1 is a sublist (or subsequence) of list2, and the task is to merge them. Specifically, the first node of list1 should point to the first node of list2, and the last node of list1 should point to the node following the node where list2 ended.

Detailed Solution:

The problem can be solved by traversing through both the linked lists. Let us define the head pointers for both linked lists as head1 and head 2 and define the starting and ending indices of the sublist of list2 to be merged into list1 as “a” and “b” respectively. The solution can be divided into the following steps:

1. Traverse through the list1 until we reach the (a-1)th node. Once we have reached that node, we can save it in a temporary variable, say temp1.

2. Similarly, traverse through the list2 until we reach the bth node. Once we have reached that node, we can save it in a temporary variable, say temp2.

3. Now, the next step is to join the list1 and list2. The next node of the temp1 should point to the head of list2, and the temp2 should point to the node following the last node of list1.

4. Finally, return head1 as the head of the merged linked list.

The following Python code implements the above solution:

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeInBetween(head1: Node, a: int, b: int, head2: Node) -> Node:
    # traverse through list1 until (a-1)th node is reached
    temp1 = head1
    for i in range(1,a):
        temp1 = temp1.next

    # traverse through list2 until bth node is reached
    temp2 = head2
    for j in range(1,b+1):
        temp2 = temp2.next

    # join list1 and list2
    temp1.next = head2
    while head2.next != None:
        head2 = head2.next
    head2.next = temp2.next

    return head1

Time Complexity:

The above solution has a time complexity of O(m+n), where “m” and “n” are the lengths of list1 and list2 respectively. As we are traversing through each linked list only once, the time complexity is O(m+n).

Space Complexity:

The above solution has a constant space complexity, O(1), as we are only using a few temporary variables to store the pointers to the linked lists. The space complexity doesn’t depend on the sizes of the input linked lists.

1