双链表的基本操作

来源：www.rxwcv.cn

双向链表的数据结构

struct ListNode {
    int val;
    struct ListNode *pre;
    struct ListNode *next;
    ListNode(int x) :
        val(x), pre(NULL), next(NULL) {
    }
}; 

双向链表的初始化

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;
}

双向链表插入元素

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;
}

双向链表删除指定元素

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;
}