Блог

В этом фрагменте кода

 Node* insert(int num, Node *head) {
 if (head == NULL|| num <= head->next)
      return addNewNode(num, head);

   head->next = insert(num, head->next);
   return head;
}
 

Почему это

 head->next = insert(num,head->next);
 

и не

 head = insert(num,head->next);
 

Я понимаю, что нам нужно пройти через односвязный список, и я подумал, что «head->next» внутри вызова функции позаботится об этом.

Если вы не вставляете элемент в качестве первого узла, вы хотите сохранить заголовок и вставить его в хвост списка.

head->next = insert(num, head->next); заменяет хвост на измененный.

head = insert(num, head->next); проигнорировал бы головку и заменил бы ее результатом вставки элемента в ее хвост.

Пример: скажем, что у нас есть

 head
 |
 v
 1 -> 3 -> X
 

и хочу вставить 2.

Рекурсивная вставка возвращает указатель на

 2 -> 3 -> X
 

и, указывая head->next на это, дает

 head
 |
 v
 1 -> 2 -> 3 -> X
 

в то время как ваше предложение дало бы

     head
     |
     v
1 -> 2 -> 3 -> X
 

и вы потеряли 1.