#include <stdio.h>
#include <malloc.h>

typedef int Elemtype;
typedef struct LNode {
    Elemtype data;
    struct LNode *next;
} LNode, *LinkList;

// 头节点初始化；
int InitList(LinkList *L) {
    (*L) = (LNode *)malloc(sizeof(LNode));
    (*L)->next = NULL;
    return 1;
}

// 头插法创建单链表；
LinkList HeadInsert(LinkList *L) {
    LNode *s;   Elemtype x;
    while (scanf("%d", &x) && x != -1) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = (*L)->next;
        (*L)->next = s;
        // 注：指针本质上就是指向的存储单元的地址；
    }
    return (*L);
}

// 顺序打印单链表数据；
void PrintList(LinkList *L) {
    LNode *p = (*L)->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
}

// WD T1;
void DelX(LinkList *L, Elemtype x) {
    LNode *p = (*L)->next, *pre = (*L);
    while (p != NULL) {
        if (p->data == x) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
        else pre = p, p = p->next;
    }
}

// WD T2;
void DelMin(LinkList *L) {
    LNode *minp = (*L)->next, *minpre = (*L), *p = minp, *pre = minpre;
    while (p != NULL) {
        if (p->data < minp->data) {
            minp = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    free(minp);
}

// WD T3 [*]链表逆置;
void ListReverse(LinkList *L) {
    // Trick1 头插法思想
    LNode *p = (*L)->next, r;
    (*L)->next = NULL;
    while (p != NULL) {
        r = p->next;
        p->next = (*L)->next;
        (*L)->next = p;
        p = r;
    }

    // Trick2 遍历修改next指向，注意r保留后继节点，由于修改next防止断链
    if ((*L)->next == NULL) return;
    // 处理特殊的第一个节点；
    LNode *pre = (*L)->next, *p = pre->next, *r;
    pre->next = NULL;
    while (p != NULL) {
        r = p->next;    // 关键步骤
        p->next = pre;
        pre = p;
        p = r;
    }
    (*L)->next = pre;
}

// WD T4;
void Del_s_t(LinkList *L, Elemtype s, Elemtype t) {
    if (s > t) return;
    LNode *pre = (*L), *p = pre->next, *q;
    while (p != NULL) {
        if (p->data >= s && p->data <= t) {
            q = p, p = p->next, pre->next = p;
            free(q);
        }
        else pre = p, p = p->next;
    }
}

// WD T5 (统考2013) 两个链表的公共节点形成的链表; 核心思路，从第一个公共节点开始之后的子链表完全相同，随后同时遍历到链表末尾指向NULL，
//                  对于不同长度的，若存在公共节点，则多出的那一截必定不可能出现公共节点，矛盾；
int NodeNum(LinkList *L) {
    int k = 0; 
    LNode *p = (*L)->next;
    while (p != NULL) k ++, p = p->next;
    return k;
}
LinkList CommonNodeList(LinkList *A, LinkList *B) {
    LinkList C = (LNode *)malloc(sizeof(LNode));
    int la = NodeNum(&(*A)), lb = NodeNum(&(*B)), dl;
    LNode *pa = (*A)->next, *pb = (*B)->next;
    if (la > lb) {
        dl = la - lb;
        while (dl --) pa = pa->next;
    }
    else {
        dl = lb - la;
        while (dl --) pb = pb->next;
    }
    while (pa != pb && pa != NULL) { pa = pa->next, pb = pb->next; }
    if (pa != NULL) printf("存在公共节点\n");
    // 建立公共节点链表；
    C->next = pa;
    return C;
}

// WD T6;
LinkList ListSplit(LinkList *L) {
    LinkList L1 = (LNode *)malloc(sizeof(LNode)), L2 = (LNode *)malloc(sizeof(LNode));
    LNode *r = (*L)->next, *p = L1, *q = L2;
    while (r != NULL) {
        p->next = r, q->next = r->next, p = p->next, q = q->next;
        r = r->next->next;  // 由于ai与bi是成对存在的，因此r非空，则r->next也非空；
    }
    // L1与L2最后一个节点的next指向NULL；
    p->next = NULL, q->next = NULL;
    (*L) = L1;
    // 针对L2进行链表翻转；
    ListReverse(&L2);
    return L2;
}

// WD T7;
void DelSame(LinkList *L) {
    if (((*L)->next) == NULL) return;

    LNode *p = (*L)->next, *q;
    while (p->next != NULL) {
        q = p->next;
        if (p->data == q->data) {
            p->next = q->next;
            free(q);
        }
        else p = q;     // 易犯错误，忘记对遍历指针进行更新，导致TL； WD T7 与 WD T6；
    }
}

// WD T8;  两个链表的公共元素形成的链表; 与T5不同的是  公共节点要求data与next都相同，而公共元素只要求data相同，不满足公共节点对应的后续子链表相同的性质；
LinkList CommonDataList(LinkList *A, LinkList *B) {
    // 有序的A、B链表；
    LinkList C = (LNode *)malloc(sizeof(LNode));
    LNode *p = (*A)->next, *q = (*B)->next, *r = C, *s;
    while (p != NULL && q != NULL) {
        if (p->data < q->data) p = p->next;
        else if (p->data > q->data) q = q->next;
        else {
            s = (LNode *)malloc(sizeof(LNode));
            s->data = p->data;
            r->next = s;
            r = s;
            p = p->next, q = q->next;
        }
    }
    r->next = NULL;
    return C;
}

// WD T9;
LinkList Union(LinkList *A, LinkList *B) {
    LNode *pa = (*A)->next, *pb = (*B)->next, *pc = (*A), *u;
    while (pa != NULL && pb != NULL) {
        if (pa->data == pb->data) {
            pc->next = pa;
            pa = pa->next;
            u = pb;
            pb = pb->next;
            free(u);
        }
        else if (pa->data < pb->data) {
            u = pa;
            pa = pa->next;
            free(u);
        }
        else {
            u = pb;
            pb = pb->next;
            free(u);
        }
    }
    while (pa != NULL) {
        u = pa;
        pa = pa->next;
        free(u);
    }
    while (pb != NULL) {
        u = pb;
        pb = pb->next;
        free(u);
    }
    pc->next = NULL;
    free(*B);
    return (*A);
}

// WD T10, 判断B是否是A的连续子序列，暴力匹配；
int Pattern(LinkList *A, LinkList *B) {
    LNode *pre = (*A)->next, *p = pre, *q = (*B)->next;
    while (p != NULL && q != NULL) {
        if (p->data == q->data) {
            p = p->next;
            q = q->next;
        }
        else {
            pre = pre->next;
            p = pre;
            q = (*B)->next;
        }
    }
    return q == NULL ? 1 : 0;
}

int main() {
    LinkList h1, h2;
    InitList(&h);   HeadInsert(&h);

    // Begin;

    // End;

    PrintList(&h);
    return 0;
}