Approach
Find the node at index a – 1 and b
Set the next of the node at index
Find the last node of list2
Set the next of the last node of list2 to the next of the node at index b
Return the head of the list
Complexity
Time complexity: O(n)
Space complexity: O(1)
Java Code
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode start = list1;
ListNode end = list1;
for (int i = 0; i < a – 1; i++) {
start = start.next;
}
for (int i = 0; i < b; i++) {
end = end.next;
}
start.next = list2;
while (list2.next != null) {
list2 = list2.next;
}
list2.next = end.next;
return list1;
}
}