在带头结点的单链表第i个结点后面插入元素x,详细解释代码
时间: 2024-03-24 18:40:26 浏览: 29
好的,下面是在带头结点的单链表第i个结点后面插入元素x的代码实现:
```C++
ListNode* insert(ListNode* head, int i, int x) {
// 判断链表是否为空
if (head == nullptr) {
return nullptr;
}
// 判断i的合法性
if (i <= 0) {
return head;
}
ListNode* pre = head;
ListNode* cur = head->next;
// 遍历链表找到第i个结点
for (int j = 1; j < i && cur != nullptr; j++) {
pre = cur;
cur = cur->next;
}
// 找不到第i个结点则无法插入
if (cur == nullptr) {
return head;
}
ListNode* newNode = new ListNode(x);
newNode->next = cur->next;
cur->next = newNode;
return head;
}
```
我们来详细解释一下这段代码的实现过程:
首先判断链表是否为空,如果为空则无法插入,直接返回头结点。
然后判断i的合法性,即i是否大于0且不超过链表长度。
遍历链表找到第i个结点,同时记录其前驱结点,如果找不到第i个结点,则无法插入,直接返回头结点。
创建一个新结点,将x赋值给新结点的数据域,并将新结点的next指针指向第i个结点的后继结点。
将第i个结点的next指针指向新结点,完成插入操作。
最后,返回头结点即可。
需要注意的是,这段代码的实现是在带头结点的单链表上进行的,若不需要头结点,则需要对其进行相应的修改。