We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Merge In Between Linked Lists

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem involves manipulating linked lists by removing a segment of one list and inserting another list in its place.
  • The indices a and b are 0-based, and we need to ensure we correctly navigate to these indices in list1.
  • A pointer approach can be effectively used to keep track of the nodes before, during, and after the insertion point.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of list1 and m is the length of list2. We traverse list1 and list2 to construct the new list.

Space Complexity: O(1) for the in-place merging, not counting the space used by the result list, as we are modifying the existing linked lists directly.

Solution

The solution involves the following steps:

  1. Traverse list1 to find the ath node and the node just before the ath node.
  2. Keep track of the bth node to know where to stop removing nodes.
  3. Connect the a-1 node to the head of list2.
  4. Connect the tail of list2 to the node after b in list1.
  5. Return the modified head of list1.

We utilize a pointer approach to perform these operations efficiently.

Code Solutions

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: Find the (a-1)th node and the bth node
    prev = None
    current = list1
    for i in range(b + 1):
        if i == a - 1:
            prev = current  # This will be the (a-1)th node
        current = current.next
    
    # Step 2: Connect (a-1)th node to the head of list2
    prev.next = list2
    
    # Step 3: Find the tail of list2 to connect to the (b+1)th node
    while list2 and list2.next:
        list2 = list2.next
    
    # Step 4: Connect the tail of list2 to the (b+1)th node
    list2.next = current
    
    return list1
← Back to All Questions