【筆記】Doubly Linked List

  • 【範例】https://neoj.sprout.tw/problem/21/
  • 接下來的M行,每行包含兩個整數:Ti, Xi
    • Ti為0的時候,代表編號Xi的玩家遭受攻擊,然後離開遊戲;
    • Ti 為1的時候,代表編號Xi的玩家使用衝刺,無條件超越當前名次比他高一名的玩家。
#include <iostream>
using namespace std;
int N, M, T, x;

struct Node{
    int val;
    Node *pre, *nxt;
    Node(int _val, Node *_pre, Node *_nxt) : val(_val), pre(_pre), nxt(_nxt) {}
};

Node *head, *tail;

void myPrint(){
    //cout << "=> ";
    Node *cur;
    cur = head;
    while (cur->nxt != NULL){
        cout << cur->val << " ";
        cur = cur->nxt;
    }
    cout << cur->val << "\n";
}

void node_swap(Node *LHS, Node *RHS){
    if (LHS->pre != NULL){
        Node *tmp;
        tmp = LHS->pre;
        tmp->nxt = RHS;
        RHS->pre = tmp;
    } else {
        RHS->pre = NULL;
        head = RHS;
    }

    LHS->pre = RHS;
    LHS->nxt = RHS->nxt;
    RHS->nxt = LHS;
    if (LHS->nxt != NULL) LHS->nxt->pre = LHS;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    head = new Node(1, NULL, NULL);
    Node *node, *cur;
    cur = head;
    for (int i = 2; i <= N; i++){
        node = new Node(i, cur, NULL);
        cur->nxt = node;
        cur = node;
    }
    //myPrint();
    while (M--){
        cin >> T >> x;
        if (T == 0){
            if (head->val == x){
                head = head->nxt;
                head->pre = NULL;
            } else {
                cur = head;
                while (cur->nxt->val != x){
                    cur = cur->nxt;
                }
                if (cur->nxt->nxt != NULL){
                    cur->nxt->nxt->pre = cur;
                }
                cur->nxt = cur->nxt->nxt;
            }
        } else {
            if (head->val != x){
                cur = head;
                while (cur->val != x){
                    cur = cur->nxt;
                }
                node_swap(cur->pre, cur);
            }
        }
        //myPrint();
    }
    myPrint();
    return 0;
}

分享本文 Share with friends