Hotstar | OA | Merge In Between (Linked Lists)
1300

Two linked lists - list1 (n nodes), list2 (m nodes)
Remove nodes a through b in list1, insert list2 in their place
Final list:
list1_1 -> ... list1_a-1 -> list2_1 ... -> list2_m ->list1_b+1 ... -> list1_n

Test Cases

Input Format: n ...n items (l1 nodes) m ... m items (l2 nodes) a b

[
   	{
   		input: '6 1 4 6 3 2 7 7 5 6 4 3 8 2 1 2 4',
   		output: '1 5 6 4 3 8 2 1 2 7',
   	},
   	{
   		input: '5 1 2 3 4 5 4 6 7 8 9 2 3',
   		output: '1 6 7 8 9 4 5',
   	},
   	{
   		input: '4 1 3 4 5 6 11 14 7 10 9 2 1 3',
   		output: '11 14 7 10 9 2 5',
   	},
   	{
   		input: '6 7 5 9 4 6 7 5 8 3 1 2 11 3 5',
   		output: '7 5 8 3 1 2 11 7',
   	},
   ]

Solution

/**
* @param {Node} list1 list1 head
* @param {Node} list2 list2 head
* @param {number} a start node for replace
* @param {number} b end node for replace
* @returns {Node} head of updated list1
*/
function mergeInBetween(list1, list2, a, b) {
   let indexA = 1
   let aPosition = list1
   while (indexA < a - 1) {
   	aPosition = aPosition.next
   	indexA++
   }

   let indexB = indexA
   let bPosition = aPosition
   while (indexB <= b) {
   	bPosition = bPosition.next
   	indexB++
   }
   aPosition.next = list2
   let current = list2
   while (current.next) {
   	current = current.next
   }
   current.next = bPosition
   if (a === 1) list1 = list1.next
   return list1
}
Comments (4)