#include<iostream>
#include<cstdio>

typedef int ElemType;
using namespace std;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LinkList;//如无特别说明，假设单链表都是带头结点的单链表
//-----------------------start-------------------------
//头插法建立单链表，时复O(n)
void CreateListF(LinkList *&L, ElemType a[], int n) {
    LinkList *s;
    int i;
    L = (LinkList *) malloc(sizeof(LinkList));//创建头节点
    L->next = NULL;
    for (i = 0; i < n; i++) {
        s = (LinkList *) malloc(sizeof(LinkList));//创建新节点
        s->data = a[i];
        s->next = L->next;//将*s插在首结点之前，头结点之后
        L->next = s;
    }
}

//------------------------end-------------------------
//-----------------------start-------------------------
//尾插法建立单链表，需增加一个尾指针r，使其始终指向当前链表的尾结点，时复为(n)
void CreateListR(LinkList *&L, ElemType a[], int n) {
    LinkList *s, *r;
    int i;
    L = (LinkList *) malloc(sizeof(LinkList));
    r = L;//r始终指向尾结点，开始时指向头结点
    for (i = 0; i < n; i++) {
        s = (LinkList *) malloc(sizeof(LinkList));//创建新节点
        s->data = a[i];
        r->next = s;//将*s插入到*r之后
        r = s;
    }
    r->next = NULL;//尾结点next置为NULL
}

//------------------------end-------------------------
//-----------------------start-------------------------
//按元素值查找，时复为O(n)
int LocateElem(LinkList *L, ElemType e) {
    LinkList *p = L->next;//p指向第一个数据节点，n置为1
    int n = 1;
    while (p != NULL && p->data != e) {
        p = p->next;
        n++;
    }
    if (p == NULL)
        return 0;//未找到，返回0
    else
        return n;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//有序单链表归并，通过复制方式建立新L3的所有结点， 没有破坏原有的L1和L2单链表，时复和空复均为O(m+n)，算法的实质是尾插法建立L3
void Merge(LinkList *L1, LinkList *L2, LinkList *L3) {
    LinkList *p = L1->next, *q = L2->next, *r, *s;
    L3 = (LinkList *) malloc(sizeof(LinkList));//创建L3的头结点
    r = L3;
    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            s = (LinkList *) malloc(sizeof(LinkList));//复制*p节点得到*s节点
            s->data = p->data;
            p = p->next;
            r->next = s;//将*s链接到L3的末尾
            r = s;
        } else {
            s = (LinkList *) malloc(sizeof(LinkList));
            s->data = q->data;
            q = q->next;
            r->next = s;
            r = s;
        }
    }
    if (q != NULL)
        p = q;
    while (p != NULL) {
        //将其中未遍历的表的余下节点复制到L3中
        s = (LinkList *) malloc(sizeof(LinkList));
        s->data = p->data;
        p = p->next;
        r->next = s;
        r = s;
    }
    r->next = NULL;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//要求空复为O(1)，会破坏L1和L2单链表
void Merge2(LinkList *L1, LinkList *L2, LinkList *&L3) {
    LinkList *p = L1->next, *q = L2->next, *r, *s = NULL;
    L3 = L1;        //利用L1的头结点作为L3的头结点
    free(L2);       //释放L2的头结点
    r = L3;         //r指向L3的尾结点
    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            r->next = p;  //将*p链接到L3的末尾
            r = s;
            p = p->next;
        } else {
            r->next = s;//将*q链接到L3的末尾
            r = s;
            q = q->next;
        }
    }
    if (q != NULL)
        p = q;//将其中未遍历的表的余下节点链接到L3中
    r->next = p;

}

//------------------------end-------------------------
//-----------------------start-------------------------
//删除单链表中第一个值为x的节点
int delx(LinkList *&L, ElemType x) {
    LinkList *pre = L, *p = pre->next;
    while (p != NULL && p->data != x) {
        pre = p;
        p = p->next;//pre，p同步后移一个节点
    }
    if (p != NULL) {//找到值为x的*p节点
        pre->next = p->next;
        free(p);
        return 1;
    } else return 0;//未找到值为x的节点
}

//------------------------end-------------------------
//-----------------------start-------------------------
//删除单链表L含两个或以上的数据节点中第一个值为x的节点的前驱节点
int delx1(LinkList *&L, ElemType x) {
    LinkList *prepre = L, *pre = prepre->next, *p;
    if (pre->data == x)
        return 0;
    p = pre->next;
    while (p != NULL && p->data != x) {
        prepre = pre;
        pre = p;
        p = p->next;//prepre，pre，p同步后移一个节点
    }
    if (p != NULL) {//找到值为x的*p节点
        prepre->next = p;//删除*pre节点
        free(pre);//释放*pre节点空间
        return 1;//成功返回1
    } else return 0;//未找到值为x的节点，返回0
}

//------------------------end-------------------------
//-----------------------start-------------------------
//判断单链表是否递增
int increase(LinkList *L) {
    LinkList *pre = L->next, *p;//pre指向第一个节点
    p = pre->next;//p指向*pre节点的后继节点
    while (p != NULL) {
        if (p->data >= pre->data) {
            pre = p;
            p = p->next;
        } else return 0;
    }
    return 1;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//在带头结点的单链表中删除一个最小值节点
void del_min_node(LinkList *&L) {
    LinkList *pre = L, *p = pre->next, *minp = p, *minpre = pre;
    while (p != NULL) {//查找最小值节点*minp及其前驱节点*minpre
        if (p->data < minp->data) {
            minp = p;//将较小节点*p存入minp中
            minpre = pre;//将较小节点的前驱*pre存入minpre中
        }
        pre = p;//pre、p同步后移
        p = p->next;
    }
    minpre->next = minp->next;//删除*minp节点
    free(minp);
}

//------------------------end-------------------------
//-----------------------start-------------------------
//删除并释放以L为表头指针的单链表的所有节点
void DestroyList(LinkList *&L) {
    LinkList *pre = L, *p = L->next;
    while (p != NULL) {
        free(pre);
        pre = p;
        p = p->next;
    }
    free(pre);//当p=NULL时还需释放*pre节点
}

//------------------------end-------------------------
//-----------------------start-------------------------
//就地逆置带头结点的单链表L
void Reverse1(LinkList *&L) {
    LinkList *p = L->next, *q;
    L->next = NULL;//将L看成只有一个头结点的空表
    while (p != NULL) {//用p遍历余下的节点
        q = p->next;//用q临时保存*p的后继节点
        p->next = L->next;//将*p节点插入到新建链表的前面
        L->next = p;
        p = q;//p继续遍历余下的节点
    }
}

//------------------------end-------------------------
//-----------------------start-------------------------
//拆分单链表成A和B，尾插法建立，A中含所有的偶数节点，B中含所有的奇数节点，时复O(n)，空复(1)
void Split(LinkList *&A, LinkList *&B) {
    LinkList *p = A->next, *ra, *rb;
    ra = A;
    B = (LinkList *) malloc(sizeof(LinkList));
    rb = B;
    while (p != NULL) {
        if (p->data % 2 == 0) {
            ra->next = p;
            ra = p;
            p = p->next;
        } else {
            rb->next = p;
            rb = p;
            p = p->next;
        }
    }
    ra->next = rb->next = NULL;
}

//------------------------end-------------------------
//-----------------------start-------------------------
/*C={a1,b1,a2,b2.....an,bn},采用带头结点的单链表hc存放，就地拆分为A和B，均带头结点
A={a1,a2...an},B={b1,b2....bn}
新建的ha采用尾插法，hb采用头插法
 */
void split1(LinkList *hc, LinkList *&ha, LinkList *&hb) {
    LinkList *p = hc->next, *ra, *q;
    ha = hc;  //ha的头节点利用hc的头节点
    ra = ha;  //ra始终指向ha的尾节点
    hb = (LinkList *) malloc(sizeof(LinkList));    //创建hb头节点
    hb->next = NULL;
    while (p != NULL) {
        ra->next = p;
        ra = p; //将奇数序号的节点*p链到ha单链表的末尾
        p = p->next;
        q = p->next;
        p->next = hb->next; //将偶数序号的节点*p插入到hb单链表的最前
        hb->next = p;
        p = q;
    }
    ra->next = NULL;    //ha的尾节点的next域置空
}
//------------------------end-------------------------
//-----------------------start-------------------------
/*L1={x1,x2...xn},L2={y1,y2...ym}，采用带头节点的链表存储，合并L1，L2，结果放在L3中，时复O(min(m,n))，空复O(1)
L3={x1,y1...xm,ym,xm+1...xn},m<=n
L3={x1,y1...xn,yn,yn+1...ym},m>n
*/
void merge(LinkList *L1, LinkList *L2, LinkList *&L3) {
    LinkList *p = L1->next, *q = L2->next, *t;
    L3 = L1;
    t = L3;
    free(L2);
    while (p != NULL && q != NULL) {
        t->next = p;
        t = p;
        p = p->next;
        t->next = q;
        t = q;
        q = q->next;
    }
    t->next = NULL;
    if (q != NULL)
        p = q;
    t->next = p;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//L1={x1,x2...xn},L2={y1,y2...ym}，通过节点重建建立L3（尾插法建表），合并L1，L2，结果放在L3中，时复O(m+n)，空复O(m+n)
void merge2(LinkList *L1, LinkList *L2, LinkList *&L3) {
    LinkList *p = L1->next, *q = L2->next, *s, *t;
    L3 = (LinkList *) malloc(sizeof(LinkList));
    t = L3;
    while (p != NULL && q != NULL) {
        s = (LinkList *) malloc(sizeof(LinkList));
        s->data = p->data;//复制产生*s节点并链到L3的末尾
        t->next = s;
        t = s;
        p = p->next;
        s = (LinkList *) malloc(sizeof(LinkList));//复制产生*s节点并链到L3的末尾
        s->data = q->data;
        t->next = s;
        t = s;
        q = q->next;
    }
    if (q != NULL)
        p = q;//让p指向未遍历完的节点
    while (p != NULL) {
        s = (LinkList *) malloc(sizeof(LinkList));
        s->data = p->data;
        p = p->next;
    }
    t->next = NULL; //t or s？？
}

//------------------------end-------------------------
//-----------------------start-------------------------
//删除带头节点单链表的奇数号节点，时复O(n)，空复(1)
void delodd(LinkList *&L) {
    LinkList *preq = L, *q = preq->next;
    while (q != NULL) {
        preq->next = q->next;
        free(q);
        preq = preq->next;//preq指向偶数号节点
        if (preq == NULL)
            break;
        q = preq->next;
    }
}

//------------------------end-------------------------
//-----------------------start-------------------------
//有序单链表L（从小到大），插入元素为x的节点后，仍然有序
void inorderList(LinkList *&L, ElemType x) {
    LinkList *s, *pre, *p;
    s = (LinkList *) malloc(sizeof(LinkList));
    s->data = x;
    s->next = NULL;
    pre = L;
    p = pre->next;
    while (p != NULL && p->data < x) {
        pre = p;
        p = p->next;
    }
    s->next = pre->next;//将*s插入到*pre之后
    pre->next = s;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//带头结点的单链表L，使其递增有序（直接插入实现）
void Sort(LinkList *&L) {
    LinkList *p = L->next, *pre, *r;
    r = p->next;//r保存*p节点后继节点的指针
    p->next = NULL;
    p = r;
    while (p != NULL) {
        r = p->next;//r保存*p节点后继节点的指针
        pre = L;
        while (pre->next != NULL && pre->next->data < p->data)
            pre = pre->next;//找到插入*p的前驱节点*pre
        p->next = pre->next;//在*pre之后插入*p节点
        pre->next = p;
        p = r;//遍历原单链表余下的节点
    }
}

//------------------------end-------------------------
//-----------------------start-------------------------
//递增单链表L，删除表中data值在[min,max]区间的节点，同时释放被删除节点的空间，时复O(n)
void delnodes(LinkList *&L, ElemType min, ElemType max) {
    LinkList *p = L->next, *q, *r = L;
    while (p != NULL && p->data < min) {//p指向刚>=min的节点
        r = p;//r为*p的前驱节点
        p = p->next;
    }
    q = p;
    while (q != NULL && q->data <= max) {//q指向刚>=max的节点
        q = q->next;
    }
    r->next = q;//删除*p到*q之前的所有结点
    r = p->next;
    while (r != q) {//释放被删结点空间
        free(p);
        p = r;
        r = r->next;
    }
}

//------------------------end-------------------------
//-----------------------start-------------------------
//删除带头结点的单链表L中data值在[min.max]之间的结点，并释放结点空间，时复O(n)，用p遍历整个单链表
void delnodes1(LinkList *&L, ElemType min, ElemType max) {
    LinkList *pre = L, *p = pre->next, *post;
    while (p != NULL) {
        if (p->data >= min && p->data <= max) {//*p结点为被删除节点，*pre为前驱节点
            post = p->next;
            pre->next = p->next;//删除*p节点
            free(p);//释放*p节点空间
            p = post;//p后移一个节点
        } else {
            pre = p;
            p = p->next;//pre、p同步后移一个节点
        }
    }
}

//------------------------end-------------------------
//-----------------------start-------------------------
//删除值域重复的节点
void dels1(LinkList *&L) {
    LinkList *p = L->next, *q, *postq, *t;
    while (p != NULL) {
        q = p;//q指向*p的后继结点？？？？？？？
        postq = q->next;//postq指向*q的后继结点
        while (postq != NULL) {
            //查找是否有与*p重复的节点
            if (postq->data == p->data) {
                //*postq是重复的节点
                t = postq->next;//t临时指向*postq的后继
                q->next = t;//删除*postq节点
                free(postq);//释放*postq节点空间
                postq = t;//postq指向下一个节点
            } else {
                q = postq;
                postq = postq->next;//q、postq同步后移一个节点
            }
        }
        p = p->next;
    }
}

//------------------------end-------------------------
//-----------------------start-------------------------
//单链表表示集合，假设单链表递增，求集合的交集，时复O(m+n)，空复O(min(m,n))
void Interset1(LinkList *A, LinkList *B, LinkList *&C) {
    LinkList *pa = A->next, *pb = B->next, *s, *r;
    C = (LinkList *) malloc(sizeof(LinkList));//建立C的头节点
    r = C;//r始终指向单链表C的尾节点？？？？？？？？？
    while (pa != NULL && pb != NULL) {
        if (pa->data < pb->data)
            pa = pa->next;
        else if (pb->data < pa->data)
            pb = pb->next;
        else {
            s = (LinkList *) malloc(sizeof(LinkList));
            s->data = pa->data;//建立一个节点
            r->next = s;
            r = s;
            pa = pa->next;
            pb = pb->next;
        }
    }
    r->next = NULL;//尾节点next置为NULL
}

//------------------------end-------------------------
//-----------------------start-------------------------
//同上，求差集，时复O(m*n)，空复O(m)，m为A中节点个数
void Diffence(LinkList *A, LinkList *B, LinkList *&C) {
    LinkList *pa = A->next, *pb, *s, *r;
    C = (LinkList *) malloc(sizeof(LinkList));//建立C的头节点
    r = C;
    while (pa != NULL) {
        pb = B->next;
        while (pb != NULL && pb->data != pa->data)
            pb = pb->next;
        if (pb == NULL) {
            //A的当前节点不在B中
            s = (LinkList *) malloc(sizeof(LinkList));
            s->data = pa->data;//建立一个复制节点
            r->next = s;
            r = s;
        }
        pa = pa->next;
    }
    r->next = NULL;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//求并集(无序)，时复O(m*n)，空复O(m*n)
void Unionset(LinkList *A, LinkList *B, LinkList *&C) {
    LinkList *pa = A->next, *pb = B->next, *s, *r;
    C = (LinkList *) malloc(sizeof(LinkList));
    r = C;
    while (pa != NULL) {
        s = (LinkList *) malloc(sizeof(LinkList));
        s->data = pa->data;
        r->next = s;
        r = s;
        pa = pa->next;
    }
    while (pb != NULL) {
        pa = A->next;
        while (pa != NULL && pa->data != pb->data)
            pa = pa->next;
        if (pa == NULL) {
            s = (LinkList *) malloc(sizeof(LinkList));
            s->data = pb->data;
            r->next = s;
            r = s;
        }
        pb = pb->next;
    }
    r->next = NULL;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//求并集（递增有序），时复O(m+n)，空复O(m+n)
void Unionset1(LinkList *A, LinkList *B, LinkList *&C) {
    LinkList *pa = A->next, *pb = B->next, *s, *r;
    C = (LinkList *) malloc(sizeof(LinkList));
    r = C;
    while (pa != NULL && pb != NULL) {
        if (pa->data < pb->data) {//仅复制*pa节点
            s = (LinkList *) malloc(sizeof(LinkList));
            s->data = pa->data;
            r->next = s;
            r = s;
            pa = pa->next;
        } else if (pb->data < pa->data) {//仅复制*pb节点
            s = (LinkList *) malloc(sizeof(LinKList));
            s->data = pb->data;
            r->next = s;
            r = s;
            pb = pb->next;
        } else {
            s = (LinkList *) malloc(sizeof(LinkList));
            s->data = pa->data;
            r->next = s;
            r = s;
            pa = pa->next;
            pb = pb->next;
        }
    }
    while (pa != NULL) {//复制A链表余下的节点
        s = (LinkList *) malloc(sizeof(LinkList));
        s->data = pa->data;
        r->next = s;
        r = s;
        pa = pa->next;
    }
    while (pb != NULL) {
        s = (LinkList *) malloc(sizeof(LinkList));
        s->data = pb->data;
        r->next = s;
        r = s;
        pb = pb->next;
    }
    r->next = NULL;
}

//------------------------end-------------------------
//-----------------------start-------------------------
//判断B是否是A的子序列
int Subseq(LinkList *A, LinkList *B) {
    LinkList *pa = A->next, *pb, *q;
    while (pa != NULL) {
        pb = B->next;
        while (pa != NULL && pa->data != pb->data)//找首元素相等的位置
            pa = pa->next;
        q = pa;
        while (q != NULL && pb != NULL && q->data == pb->data) {
            //若对应的节点值相同，则同步后移
            q = q->next;
            pb = pb->next;
        }
        if (pb == NULL)//B序列比较完毕
            return 1;
        else if (pa != NULL)//若A序列未遍历完，则从下一个节点开始重复进行
            pa = pa->next;
    }
    return 0;
}
//------------------------end-------------------------