双向链表的数据结构

1
2
3
4
5
6
7
8
struct ListNode {
int val;
struct ListNode *pre;
struct ListNode *next;
ListNode(int x) :
val(x), pre(NULL), next(NULL) {
}
};

双向链表的初始化

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* createList() {
ListNode* head = new ListNode(-1);
ListNode* node = head;
vector<int> nums = { 1,2,3 };
for (int i = 0; i < nums.size(); ++i) {
ListNode* temp = new ListNode(nums[i]);
node->next = temp;
temp->pre = node;
node = node->next;
}
return head;
}

双向链表插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* insertNode(ListNode* head, int pos, int elem) {
ListNode* node = head;
int i = 0;
while (node->next && i < pos - 1) {
node = node->next;
++i;
}
if (!node || i > pos - 1) {
cout << "插入失败!" << endl;
return node;
}
ListNode* temp = new ListNode(elem);
node->next->pre = temp;
temp->next = node->next;
node->next = temp;
temp->pre = node;
return head;
}

双向链表删除指定元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* deleteNode(ListNode* head, int pos) {
ListNode* node = head;
int i = 0;
while (node->next && i < pos - 1) {
node = node->next;
++i;
}
if (!node || i > pos - 1) {
cout << "删除失败!" << endl;
return head;
}
ListNode* del = node->next;
node->next = del->next;
del->next->pre = node;
delete del;
del = nullptr;
return head;
}