双链表操作（不带头结点）

struct Node {    int val;    struct Node* prior, *next;    Node(int v) : val(v) { prior = NULL; next = NULL; }};

构建双链表

struct Node* build() {    struct Node* head = NULL;    struct Node* ptr = NULL;    int val;     while (cin >> val) {        if (head == NULL) {            head = new Node(val);            head->next = head;            ptr = head;        }        else {            ptr->next = new Node(val);            ptr->next->prior = ptr;            ptr = ptr->next;        }    }    if (head != NULL) {        head->prior = ptr;        ptr->next = head;    }    return head; }

遍历

//升序遍历void ascendingTraverse(struct Node* head) {    if (head == NULL)        return;    auto ptr = head;    do {        cout << ptr->val;        ptr = ptr->next;        if (ptr == head) {            cout << endl;        }        else {            cout << " ";        }    } while (ptr != head);}// 逆序遍历void descendingTraverse(struct Node* head) {    if (head == NULL)        return;    auto ptr = head->prior;    do {        cout << ptr->val;        ptr = ptr->prior;        if (ptr == head->prior) {            cout << endl;        }        else {            cout << " ";        }    } while (ptr != head->prior);}

插入排序 重点

/*移动结点内的元素，而不是结点本身*//*注意head会发生变化*/void sort(struct Node*& head) {     if (!head)        return;    for (auto ptr = head->next; ptr != head; ptr = ptr->next) {        int tmp = ptr->val;         struct Node* pri;        /* 注意该条件：pri != head->prior */        for (pri = ptr->prior; pri != head->prior && pri->val > tmp ; pri = pri->prior){            pri->next->val = pri->val;         }        pri->next->val = tmp;     }    int minNum = head->val;    auto newHead = head;     for (auto ptr = head->next; ptr != head; ptr = ptr->next) {        if (minNum > ptr->val) {            newHead = ptr;            minNum = ptr->val;        }    }    head = newHead; }

删除

void destroy(struct Node* head) {    if (!head)        return;    for (auto ptr = head->next; ptr != head; ) {        auto tmp = ptr->next;        delete ptr;        ptr = tmp;     }    delete head;}