Merge In Between Linked Lists
Merge In Between Linked Lists is a medium linked list problem solved with the miscellaneous pattern.
The best approach, optimal (splice in place), runs in O(n + m) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rebuild through an array) up.
Problem
You are given two singly linked lists, list1 and list2, and two indices a and b (0-based). Remove the nodes of list1 at positions a through b, inclusive, and put the whole of list2 in their place.
Return the head of the resulting list. Neither the first nor the last node of list1 is ever removed.
Examples
Example 1
- Input
list1 = [4, 8, 15, 16, 23, 42], a = 2, b = 3, list2 = [7, 9]- Output
[4, 8, 7, 9, 23, 42]- Why
- Nodes at indices 2 and 3 (values 15 and 16) are cut out and [7, 9] is spliced into the gap.
Example 2
- Input
list1 = [1, 2, 3], a = 1, b = 1, list2 = [50, 60, 70]- Output
[1, 50, 60, 70, 3]- Why
- Only the middle node is removed; all of list2 goes where it was.
Constraints
3 <= list1.length <= 10^41 <= a <= b < list1.length - 11 <= list2.length <= 10^4-10^4 <= Node.val <= 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (rebuild through an array) | O(n + m) | O(n + m) |
| Optimal (splice in place) | O(n + m) | O(1) |
1Brute force (rebuild through an array)
O(n + m)Each node of both lists is visited a constant number of times.O(n + m)The value array and the brand-new list hold n + m entries.Copy the values you want to keep into an array in the final order: list1 before index a, all of list2, then list1 after index b. Build a fresh linked list from that array.
- Walk list1 with an index; add values with index < a to the array.
- Add every value of list2.
- Walk list1 again; add values with index > b.
- Create new nodes from the array behind a dummy head and return dummy.next.
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
List<Integer> vals = new ArrayList<>();
int i = 0;
for (ListNode p = list1; p != null; p = p.next, i++) {
if (i < a) vals.add(p.val);
}
for (ListNode p = list2; p != null; p = p.next) vals.add(p.val);
i = 0;
for (ListNode p = list1; p != null; p = p.next, i++) {
if (i > b) vals.add(p.val);
}
ListNode dummy = new ListNode(0), tail = dummy;
for (int v : vals) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
}class Solution:
def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
vals = []
p, i = list1, 0
while p:
if i < a:
vals.append(p.val)
p, i = p.next, i + 1
p = list2
while p:
vals.append(p.val)
p = p.next
p, i = list1, 0
while p:
if i > b:
vals.append(p.val)
p, i = p.next, i + 1
dummy = ListNode(0)
tail = dummy
for v in vals:
tail.next = ListNode(v)
tail = tail.next
return dummy.nextclass Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
vector<int> vals;
int i = 0;
for (ListNode* p = list1; p != nullptr; p = p->next, i++) {
if (i < a) vals.push_back(p->val);
}
for (ListNode* p = list2; p != nullptr; p = p->next) vals.push_back(p->val);
i = 0;
for (ListNode* p = list1; p != nullptr; p = p->next, i++) {
if (i > b) vals.push_back(p->val);
}
ListNode dummy(0);
ListNode* tail = &dummy;
for (int v : vals) {
tail->next = new ListNode(v);
tail = tail->next;
}
return dummy.next;
}
};function mergeInBetween(list1, a, b, list2) {
const vals = [];
let i = 0;
for (let p = list1; p !== null; p = p.next, i++) {
if (i < a) vals.push(p.val);
}
for (let p = list2; p !== null; p = p.next) vals.push(p.val);
i = 0;
for (let p = list1; p !== null; p = p.next, i++) {
if (i > b) vals.push(p.val);
}
const dummy = new ListNode(0);
let tail = dummy;
for (const v of vals) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}2Optimal (splice in place)
O(n + m)At most one walk through list1 (up to index b + 1) and one through list2.O(1)Only three pointers; the existing nodes are relinked.Find the node at index a - 1 (before) and the node at index b + 1 (after) in list1, and the last node of list2. Point before.next at list2's head and the tail's next at after. No new nodes are created.
- Walk a - 1 steps from list1 to get before.
- From before, walk b - a + 2 more steps to get after (the node at index b + 1).
- Walk list2 to its last node, tail2.
- Set before.next = list2 and tail2.next = after; return list1.
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode before = list1;
for (int i = 0; i < a - 1; i++) before = before.next;
ListNode after = before;
for (int i = 0; i < b - a + 2; i++) after = after.next;
ListNode tail2 = list2;
while (tail2.next != null) tail2 = tail2.next;
before.next = list2;
tail2.next = after;
return list1;
}
}class Solution:
def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
before = list1
for _ in range(a - 1):
before = before.next
after = before
for _ in range(b - a + 2):
after = after.next
tail2 = list2
while tail2.next:
tail2 = tail2.next
before.next = list2
tail2.next = after
return list1class Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
ListNode* before = list1;
for (int i = 0; i < a - 1; i++) before = before->next;
ListNode* after = before;
for (int i = 0; i < b - a + 2; i++) after = after->next;
ListNode* tail2 = list2;
while (tail2->next != nullptr) tail2 = tail2->next;
before->next = list2;
tail2->next = after;
return list1;
}
};function mergeInBetween(list1, a, b, list2) {
let before = list1;
for (let i = 0; i < a - 1; i++) before = before.next;
let after = before;
for (let i = 0; i < b - a + 2; i++) after = after.next;
let tail2 = list2;
while (tail2.next !== null) tail2 = tail2.next;
before.next = list2;
tail2.next = after;
return list1;
}Edge cases to test
- a == b: exactly one node is removed
- a = 1 and b = length - 2: everything but the first and last node is replaced
- list2 has a single node
Hints
Hint 1
You need two anchors in list1: the node just before index a and the node just after index b.
Hint 2
You also need the tail of list2, so the node after b can be hooked onto it.
Hint 3
Once you have the three nodes, the splice is two pointer assignments.
FAQ
What is the best time complexity for Merge In Between Linked Lists?
Optimal (splice in place) runs in O(n + m) time and O(1) extra space. At most one walk through list1 (up to index b + 1) and one through list2.
Which pattern does Merge In Between Linked Lists use?
It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Copy List with Random Pointer, Intersection of Two Linked Lists.
Is there a brute force solution for Merge In Between Linked Lists?
Yes. Brute force (rebuild through an array) takes O(n + m) time and O(n + m) space. Copy the values you want to keep into an array in the final order: list1 before index a, all of list2, then list1 after index b.
Which edge cases should I test for Merge In Between Linked Lists?
a == b: exactly one node is removed; a = 1 and b = length - 2: everything but the first and last node is replaced; list2 has a single node.