在双向链表第i个位置插入元素e
时间: 2024-05-07 07:20:11 浏览: 13
假设双向链表的头节点为head,节点结构体的定义如下:
```
struct ListNode {
int val;
ListNode *prev;
ListNode *next;
ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};
```
则可以按照以下步骤在第i个位置插入元素e:
1. 新建一个节点newNode,将它的值设为e。
2. 如果i等于1,将newNode作为新的头节点,把head的前驱指针指向newNode,newNode的后继指针指向head,返回。
3. 从头节点开始遍历链表,找到第i-1个节点node和第i个节点nextNode。
4. 将newNode的前驱指针指向node,后继指针指向nextNode。
5. 将node的后继指针指向newNode,nextNode的前驱指针指向newNode。
6. 返回。
下面是代码实现:
```
ListNode* insert(ListNode* head, int i, int e) {
ListNode* newNode = new ListNode(e);
if (i == 1) {
newNode->next = head;
head->prev = newNode;
return newNode;
}
ListNode* node = head;
for (int j = 1; j < i - 1; j++) {
node = node->next;
}
ListNode* nextNode = node->next;
newNode->prev = node;
newNode->next = nextNode;
node->next = newNode;
nextNode->prev = newNode;
return head;
}
```