LeetCode Solutions Blog

Merge In Between Linked Lists

Number: 1765

Difficulty: Medium

Paid? No

Problem Description

Given two linked lists, list1 and list2, remove the nodes of list1 from the ath node to the bth node (inclusive) and insert list2 in their place. Then, return the head of the modified list.

Key Insights

Traverse list1 to find the node right before index a.
Continue traversal to locate the node immediately after index b.
Find the tail of list2.
Reconnect these parts: connect the node before a to the head of list2 and connect list2's tail to the node after b.

Space and Time Complexity

Time Complexity: O(n1 + n2) where n1 is the length of list1, and n2 is the length of list2. Space Complexity: O(1) assuming we perform pointer manipulation in-place.

Solution

We solve the problem by performing the following steps:

Traverse list1 to obtain the node just before the ath node (let's call it prevA).
Continue traversing list1 from prevA to get to the node right after the bth node (postB).
Traverse list2 to locate its tail.
Link prevA.next to list2's head.
Link list2's tail to postB. This reconnects list1 with list2 in-between, effectively removing the nodes from a to b.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeInBetween(list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
    # Step 1: Traverse list1 to reach node just before index a (prevA)
    current = list1
    for i in range(a - 1):
        current = current.next
    prevA = current
    
    # Step 2: Continue traversing to reach node after index b (postB)
    current = current.next
    for i in range(b - a + 1):
        current = current.next
    postB = current
    
    # Step 3: Find the tail of list2
    tail2 = list2
    while tail2.next:
        tail2 = tail2.next
    
    # Step 4: Connect list2 between list1 parts
    prevA.next = list2       # Connect node before index a to head of list2
    tail2.next = postB       # Connect tail of list2 to node after index b
    
    return list1           # Return the modified list1