Как вставить узел в односвязный список в заданную позицию с помощью рекурсии

Учитывая односвязный список как список , позицию и узел , задача состоит в том, чтобы вставить этот элемент в данный связанный список в заданную позицию, используя рекурсию .

Примеры:

Input: list = 1->2->3->4->5->6->7, node = (val=100,next=null), position = 4 
Output: 1->2->3->100->4->5->6->7
Explanation: Here the node with value 100 is being inserted at the 4th position. Initially at the 4th position the value is 4. Now when 100 is inserted at 4th position all the value starting from 4 will shift 1 position to its right. This can be visualised in the following way:

1->2->3->4->5->6->7
1->2->3->100->4->5->6->7

Input: list = 1->2->3->100->4->5->6->7, node = (val=101,next=null), position = 1  
Output: 10->1->2->3->100->4->5->6->7

Решение:

Будет 3 случая :

1. Вставить узел в первую позицию связанного списка
   • Подход: следуйте шагам, указанным ниже:
     1. Создайте временный узел.
     2. Теперь вставьте временный узел перед головой и измените указатель головы, чтобы он указывал на временный узел.
2. Вставьте узел между первым и последним узлами связанного списка
   • Подход: следуйте шагам, указанным ниже:
     1. Вызовите рекурсивную функцию, чтобы добраться до нужной позиции.
     2. Если позиция больше длины списка, вставка невозможна.
     3. Если нет, то вставьте новый узел в нужное место.
3. Вставить узел в конец связанного списка
   • Подход: следуйте шагам, указанным ниже:
     1. Рекурсивно перейти в конец связанного списка.
     2. Вставьте новый узел в конец списка.

Рекуррентное соотношение: T(n) = T(n-1) + c

Ниже приведена реализация вышеуказанного подхода.

Временная сложность: O(N), где N — размер связанного списка.
Вспомогательное пространство: O(N), где N — размер связанного списка.

Более простой подход к приведенному выше коду C++: