{x}
blog image

Merge In Between Linked Lists

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:

Build the result list and return its head.

 

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.

Example 2:

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

 

Constraints:

  • 3 <= list1.length <= 104
  • 1 <= a <= b < list1.length - 1
  • 1 <= list2.length <= 104

1669. Merge In Between Linked Lists

Problem Description

Given two linked lists, list1 and list2, remove nodes from list1 starting from the a-th node to the b-th node (inclusive) and insert list2 in their place. Return the head of the modified list1.

Approach: Simulation

The solution directly simulates the merge operation. We traverse list1 to find the nodes just before the a-th node and the b-th node. Then, we link the node before a to the head of list2 and the tail of list2 to the node after b.

Algorithm

  1. Initialization: Two pointers, p and q, are initialized to the head of list1.
  2. Finding the Split Points: p is moved a-1 steps to reach the node before the a-th node. q is moved b steps to reach the b-th node.
  3. Merging: The next pointer of p is set to the head of list2.
  4. Finding the Tail of list2: We traverse list2 until we reach its tail (p will now point to the tail of list2).
  5. Connecting the Tails: The next pointer of p is set to the node after b (which is q.next).
  6. Cleaning up: q.next is set to null to detach the removed section from list1.
  7. Return: The head of the modified list1 is returned.

Time and Space Complexity

  • Time Complexity: O(m + n), where 'm' is the length of list1 and 'n' is the length of list2. We traverse list1 to find the split points and traverse list2 to find its tail.
  • Space Complexity: O(1). We use only a constant amount of extra space for pointers.

Code Implementation

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
 
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        p = q = list1
        for _ in range(a - 1):
            p = p.next
        for _ in range(b + 1): #Corrected the loop condition here
            q = q.next
        p.next = list2
        while p.next:
            p = p.next
        p.next = q
        return list1

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode p = list1, q = list1;
        for (int i = 0; i < a - 1; ++i) p = p.next;
        for (int i = 0; i <= b; ++i) q = q.next;
        p.next = list2;
        while (p.next != null) p = p.next;
        p.next = q;
        return list1;
    }
}

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode* p = list1, *q = list1;
        for (int i = 0; i < a - 1; ++i) p = p->next;
        for (int i = 0; i <= b; ++i) q = q->next;
        p->next = list2;
        while (p->next != nullptr) p = p->next;
        p->next = q;
        return list1;
    }
};

(Other languages like Go, TypeScript, and C# would follow a similar structure, adapting syntax as needed.)

Note: The code examples provided are optimized for clarity and conciseness. Error handling (e.g., checking for null pointers or invalid input) could be added for robustness in a production environment.