小L的编辑器

C - 小L的编辑器 之 复杂的写法(指针+链表)

粗读题意就能发现在数据处理的过程中需要频繁的插入数据，能够在O(1)的时间内完成数据插入，首先就能想到学过的链表，所以我们就能开始复杂的指针+链表解题了。

#include<stdio.h>
#include<string.h>

const int N = 1e6 + 10;
char s[N],t[N];
struct node{
    char c;
    node *next,*l;//next 指下一个节点，l 指上一个节点。因为插入的位置可能是左也可能是右
};

int main(){
    scanf("%s %s",s,t);
    int n = strlen(s);
    node *p = new node(),*hand = new node();
    p -> c = s[0];
    p -> next = NULL;
    p -> l = NULL;
    hand -> l = NULL; 
    hand -> next = p;
    p -> l = hand;
    bool inq = true;
    for(int i=1;i<n;i++) {
        node *q = new node();
        q -> next = NULL;
        q -> l = NULL;
        q -> c = s[i];
        if(t[i-1] == 'L'){
            q -> next = p;
            p -> l -> next = q;
            q -> l = p -> l;
            p -> l = q;
            p = q;
            if(inq && t[i] == 'R'){ // 特判头节点
                inq = false;
                hand -> next = p;
                p -> l = hand;
            }
        }
        else {
            inq = false;
            q -> next = p -> next;
            p -> next = q;
            q -> l = p;
            p = q;
        }
    }
    if(inq) hand -> next = p;
    hand = hand -> next;
    while(hand != NULL){
        printf("%c",hand -> c);
        hand = hand -> next;
    }
    return 0;
}