创建一个函数以在给定位置将元素插入到列表中

Question

不确定是否有简单更好的方法来实现此功能？

void insert(Node* &head, int element, int position) {
Node* current = new Node;
current->data = element;
current->next = NULL;
if (position == 1) {
current->next = head;
head = current;
return;
}
else {
Node * current2 = head;
for (int i = 0; i < position - 2; i++) {
current2 = current2->next;
}
current2->next = current2->next;
current2->next = current;
}
} 

Answer 1

更好的方法是使此函数没有空指针访问。您缺少所有必要的错误检查。

但是，如果您必须使用此功能，那么您已经做错了什么。该操作需要 O(n( 时间。如果你只使用这个函数来构建你的列表，那么你已经有O(n^2(时间了。使用平衡的树或堆会给你 O(n * log n( 时间，即使对于相对较小的 n 也会产生巨大的差异。因此，请再次考虑为什么需要在给定位置插入并考虑更合适的数据结构。

一个更简单的实现，实际上在实际代码中大量使用，是使用双向链表实现insert_before(before, data)或insert_after(after, data)。两者都会在列表中获得一个项目，并在 O(1( 时间在旧项目之前或之后插入和放置一个新项目。

Answer 2

需要进行一些边界检查(请找到内联注释(：

int listLen(Node *head)
{
int len = 0;
while (head != nullptr)
{
len++;
head = head->next;
}
return len;
}
void insert(Node* &head, int element, int position)
{
if (head == nullptr)    // do nothing if head is nullptr
return;
if (position < 0)   // insert to the begin if position is negative
position = 0;
else
{
int len = listLen(head);
if (len < position)   // position is out of range, insert to the end
{
position = len;
}
}
if (position == 0)
{
Node *next = head;
head = new Node(element);
head->next = next;
}
else
{
int curPos = 0;
Node *curNode = head;
while (curPos < position - 1)   // move to position
{
curNode = curNode->next;
curPos++;
}
Node *next = curNode->next;    // do insertion
curNode->next = new Node(element);
curNode->next->next = next;
}
}