Объединить два LinkedList без создания нового LinkedList

Это объединение вставляет узлы, которые были скопированы или будут украдены из списка источников, в целевой список в определенных позициях.

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

Что полезно для операции копирования и вставки, так это итератор — то, что указывает на узел и, после ++-op указывает на следующий узел в списке или за концом списка (эквиваленту nullptr):

(Я пишу такие фрагменты в одном исходном файле; переместить реализации в файлы .cpp или встроить их)

//
#include <type_traits>
using std::conditional;
#include <stdexcept>
using std::runtime_error;

class LinkedList
{private:
// [...]

template <bool const_tag>
struct NodeIterator {
using element_type = typename conditional<
const_tag,
const ListNode,
ListNode
>::type;
using pointer_type = element_type*;
using reference_type = element_type&;

static const NodeIterator end;

NodeIterator(pointer_type p_in = nullptr) : p(p_in) {}

NodeIterator& operator++ () {
if (nullptr == p)
throw runtime_error("Attempt to dereference nullptr");
this->p = p->next;
return *this;
}

bool operator== (const NodeIterator& rhs) const {
return this->p != rhs.p;
}

bool operator!= (const NodeIterator& rhs) const {
return !(*this == rhs);
}

pointer_type operator->() const {
return p;
}

reference_type operator*() const {
if (nullptr == p)
throw runtime_error("Attempt to dereference nullptr");
return *p;
}

private:
pointer_type p;
}; // template <bool const_tag> struct NodeIterator

static constexpr bool mutable_tag = false;
static constexpr bool const_tag = true;

using iterator_type = NodeIterator<mutable_tag>;
using const_iterator_type = NodeIterator<const_tag>;public:
LinkedList() :  head(nullptr) {}

iterator_type begin() const { return iterator_type(head); }
const iterator_type& end() const { return iterator_type::end; }

const_iterator_type cbegin() const { return const_iterator_type(head); }
const const_iterator_type& cend() const { return const_iterator_type::end; }
// [...]}; // class LinkedList// [...]
template<bool is_const>
const LinkedList::NodeIterator<is_const>
LinkedList::NodeIterator<is_const>::end(nullptr);

// [...]

Теперь в коде функции слияния вы размещаете свои итераторы во главе соответствующих списков.

auto it_one = listOne.begin();
auto it_two = listTwo.cbegin();

и приращение it_one пока он не будет указывать на элемент целевого списка, после которого должна быть вставлена ​​копия, и приращения it_two пока он не укажет на узел списка источников, который будет скопирован, затем

ListNode& one = *it_one;
ListNode* ptwo = new ListNode(*it_two); // copies

ptwo->next = one.next;
one.next = ptwo;

И это все по сути.

Таким образом, реальная проблема здесь не в том, как объединить технически, а в сложности операций.

Пока оба списка отсортированы в предполагаемом порядке создаваемого списка результатов, вы можете повторно использовать итераторы, и, таким образом, просто просматривать оба списка, и это O(N) с N = max(size(listOne), size(listTwo)),

Если вам необходимо предварительно отсортировать их, чтобы сохранить объединение дешево, то сортировка вызывает O(N log N) сложность.

Как примечание, наличие итераторов в хранилище также упрощает реализацию других операций; например отображение их просто

for (const auto& node : ListOne) {
std::cout << node.firstName << std::endl;
std::cout << node.lastName << std::endl;
std::cout << node.phoneNumber << std::endl;
}