При выполнении операции объединения для двух неупорядоченных связанных списков может ли сложность времени быть O (1)?

Question

В настоящее время у меня есть метод, который добавляет один связанный список (list2) в конец другого (list1). Это происходит через некоторое время l oop, при этом каждая итерация добавляет следующий узел от конца list1 к концу list2 и т. Д.

Насколько я понимаю, это будет O (n) сложность времени, так как количество итераций в то время как l oop напрямую определяется размером list2. Если list2 имеет 15 узлов, функция выполняет 15 добавлений, если list2 имеет 1000 узлов, она выполняет 1000 добавлений.

Часто, однако, я продолжаю видеть, что люди отмечают, что это объединение может быть выполнено за O (1) времени сложность, если вы держите указатель на хвост list1. Как это возможно? Из моего (по общему признанию ограниченного) понимания я могу в некоторой степени понять, что отдельные добавления - это O (1), но если вы добавляете целый список, это не обязательно должно быть в то время как l oop и сканирование всего списка2 независимо, следовательно, O (n)?

Answer 1

Ключ в том, что вам не нужно добавлять весь список. list2 - это уже связанный список, каждый элемент которого связан со следующим элементом, поэтому, если ваш список содержит ссылку на первый и последний элементы, все, что вам действительно нужно сделать, это связать их вместе. В псевдокоде:

list1.tail.next = list2.head
union.head = list1.head
union.tail = list2.tail