Скопировать связанный список с дополнительным случайным указателем без использования дополнительной памяти и сложностью алгоритма O(n)

struct list_item {
	list_item *next; // указатель на следующий элемент списка 
	list_item *rand; // указатель на произвольный элемент списка 
};

list_item *first; // указатель на первый элемент списка 

list_item copy(){
	int length = 0;
	
	// вычисляем длину списка
	list_item *current = first;
	while(current != NULL){
		current = current->next;
		length++;
	}

	// выделяем область памяти, необходимую для хранения копии списка
	// таким образом, у нас есть доступ к списку как по индексу, так
	// и через связывающий указатель. в этом случае связывающий указатель
	// next можно заполнить во время второго прохода, и его можно
	// использовать для хранения промежуточных данных
	list_item *new = malloc(length * sizeof(list_item));
	
  // меняем списоки следующим образом:
  // поле next нового списка содержит ссылку на копируемый элемент старого списка
  // поле next старого списка содержит порядковый номер элемента
  int i = 0;
	current = first;
  list_item *next;
	while(current != NULL){
    new[i].next = current;
    next = current.next;
    current.next = i;
    current = next;
  }
	
	// теперь мы можем воссоздать в новом списке такую же связанность через
	// связывающий указатель rand, как и в исходном, так как мы можем узнать
	// индекс элемента, на который указывает указатель rand, он записан в поле
	// next старого списка
	current = first;
  for(i = 0; i<length; i++){
    int index = current.rand.next;
    new[i].rand = &new[index];
  }
  
  // в этом цикле восстановливаем связанность через next исходного списка,
  // которая была нарушена для воссоздания связанности через rand в новом.
  // стоить отметить, что указатель на следующий элемент старого находится в
  // поле next следующего элемента нового массива, то цикл ведём до length-1
	current = first;
  for(i = 0; i<length-1; i++){
    current.next = new[i+1].next;
    current = current.next;
  }
  // важно: последнему элементу устанавливаем NULL в качестве NEXT, так как
  // во время установки ему было назначего не-NULL значение, и индикатор конца
  // списка оказался неопределённым
  current.next = NULL;

  // во время последнего прохода выставляем связку по next для нового списка.
  // цикл ведём до length-1, так как последний элемент не должен указывать
  // на какой-то другой
  for(i = 0; i<length-1; i++){
    new[i].next = &new[i+1]
  }
  // опять же, для последнего элемента нового списка устанавливаем указатель
  // next в NULL для индикации конца списка
  new[length-1].next = NULL;
	
  return new;
}