在第i个结点前插入值为x的结点
时间: 2023-06-01 16:01:30 浏览: 286
算法思路:
1.创建一个新的结点,值为x。
2.如果要插入的位置是链表的第一个结点,则将新结点的next指针指向头结点,然后将头结点指向新结点。
3.如果要插入的位置不是链表的第一个结点,则需要遍历链表找到要插入位置的前一个结点。遍历过程中,需要记录当前结点和前一个结点的位置。
4.找到要插入位置的前一个结点后,将新结点的next指针指向当前结点,然后将前一个结点的next指针指向新结点。
5.插入完成后,返回链表的头结点。
代码实现:
```
ListNode* insertNode(ListNode* head, int x, int i) {
ListNode* newNode = new ListNode(x);
if (i == 1) {
newNode->next = head;
head = newNode;
} else {
ListNode* cur = head;
ListNode* pre = NULL;
int j = 1;
while (cur != NULL && j < i) {
pre = cur;
cur = cur->next;
j++;
}
pre->next = newNode;
newNode->next = cur;
}
return head;
}
```
算法分析:
时间复杂度:O(n),需要遍历整个链表找到插入位置的前一个结点。
空间复杂度:O(1),只需要常数个额外的空间。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)