1669. Merge In Between Linked Lists LeetCode Solution
In this guide, you will get 1669. Merge In Between Linked Lists LeetCode Solution with the best time and space complexity. The solution to Merge In Between Linked Lists problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1669. Merge In Between Linked Lists LeetCode Solution in C++
class Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
ListNode* nodeBeforeA = list1;
for (int i = 0; i < a - 1; ++i)
nodeBeforeA = nodeBeforeA->next;
ListNode* nodeB = nodeBeforeA->next;
for (int i = 0; i < b - a; ++i)
nodeB = nodeB->next;
nodeBeforeA->next = list2;
ListNode* lastNodeInList2 = list2;
while (lastNodeInList2->next != nullptr)
lastNodeInList2 = lastNodeInList2->next;
lastNodeInList2->next = nodeB->next;
nodeB->next = nullptr;
return list1;
}
}; /* code provided by PROGIEZ */
1669. Merge In Between Linked Lists LeetCode Solution in Java
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode nodeBeforeA = list1;
for (int i = 0; i < a - 1; ++i)
nodeBeforeA = nodeBeforeA.next;
ListNode nodeB = nodeBeforeA.next;
for (int i = 0; i < b - a; ++i)
nodeB = nodeB.next;
nodeBeforeA.next = list2;
ListNode lastNodeInList2 = list2;
while (lastNodeInList2.next != null)
lastNodeInList2 = lastNodeInList2.next;
lastNodeInList2.next = nodeB.next;
nodeB.next = null;
return list1;
}
} // code provided by PROGIEZ
1669. Merge In Between Linked Lists LeetCode Solution in Python
class Solution:
def mergeInBetween(
self,
list1: ListNode,
a: int,
b: int,
list2: ListNode,
) -> ListNode:
nodeBeforeA = list1
for i in range(a - 1):
nodeBeforeA = nodeBeforeA.next
nodeB = nodeBeforeA.next
for i in range(b - a):
nodeB = nodeB.next
nodeBeforeA.next = list2
lastNodeInList2 = list2
while lastNodeInList2.next:
lastNodeInList2 = lastNodeInList2.next
lastNodeInList2.next = nodeB.next
nodeB.next = None
return list1 # code by PROGIEZ
