/* 
    链表
 */

#include<iostream>

using namespace std;

//单链表结点类型描述
typedef struct Lnode{
    ElemType data;
    struct Lnode *next;
}LNode, *LinkList;

//双链表
typedef struct DNode{
    ElemType data;
    int freq;
    struct DNode *prior, *next;
}DNode, *DLinkList;

/* 1. 递归地删除不带头结点的单链表L中所有值为x的结点 */
void Dele_X(LinkList &L, ElemType x){
    LNode *p;
    if (L == NULL) return;
    if (L->data == x){
        p = L;
        L = L->next;
        free(p);
        Dele_X(L, x);
    }
    else
        Dele_X(L->next, x);
}

/* 2. 删除带头结点的单链表L中所有值为x的结点 */
void Dele_X(LinkList &L, ElemType x){
    LNode *pre = L, *p = L->next, *q;
    while (p != NULL){
        if (p->data == x){
            q = p;
            p = p->next;
            pre->next = p->next;
            free(q); 
        }
        else
        {
            pre = p;
            p = p->next;
        }
    }
}

/* 3. 反向输出单链表L结点的值 */
void R_Print(LinkList L){
    if (L->next != NULL)
        R_Print(L->next);
    if(L != NULL)
        printf("%d", L->data);
}

/* 4. 删除带头结点的单链表中的最小值（唯一） */
void Dele_Min(LinkList &L){
    LNode *pre = L, *p = L->next;       //pre指向前驱结点， p为工作指针
    LNode *minPre = pre, *minP = p;     //最小结点前驱及最小结点
    while (p != NULL){
        if (p->data < minP->next){
            minPre = pre;
            minP = p;
        }
        p = p->next;
        pre = p;
    }
    minPre->next = minP->next;
    free(minP);
}

/* 5. 将带头结点的单链表就地逆置 */
void Reverse(LinkList &L){
    //采用头插法逆置
    LNode *p = L->next, *r;
    L->next = NULL;
    while(p != NULL){
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
}

/* 6. 带头结点的单链表，使其元素递增有序 */
void Sort(LinkList &L){
    LNode *p = L->next, *pre;
    Lnode *r = p->next;
    p->next = NULL;
    p = r;
    while(p != NULL){
        r = p->next;
        pre = L;
        while(pre->next != NULL && pre->next->data < p->data)
            pre = pre->next;
        p->next = pre->next;
        pre->next = p;
        p = r;
    }
}

/* 7. 删除无序带头结点的单链表中在给定区间的元素 */
void RangeDelete(LinkList &L, int min, int max){
    LNode *pre = L, *p = L->next;
    while(p != NULL){
        if (p->data >= min && p->data <= max){
            pre->next = p->next;
            p = p->next;
            free(p);
        }
        else{
            pre = p;
            p = p->next;
        }
    }
}

/* 8. 给定两个单链表，找出这两个结点的公共结点 */
LinkList Search_1st_Common(LinkList L1, LinkList L2){
    int len1 = Length(L1), len2 = Length(L2), dis;
    LinkList longList, shortList;
    if (len1 < len2){
        longList = L2;
        shortList = L1;
        dis = len2 - len1;
    }
    else{
        longList = L1;
        shortList = L2;
        dis = len1 - len2;
    }
    while(dis--)
        longList = longList->next;
    while(longList != NULL){
        if(shortList == longList)
            return longList;
        else{
            longList = longList->next;
            shortList = shortList->next;
        }
    }
    return NULL;
}

/* 9. 按递增次数输出带头结点单链表，并释放结点所占空间（不允许用数组做辅助空间） */
void Min_Dele(LinkList &head){
    LNode *pre, *p, *u;
    while(head->next != NULL){
        pre = head;
        p = pre->next;
        while(p != NULL){
            if (p->next->data < pre->next->data)
                pre = p;
            p = p->next;
        }
        printf(pre->next->data);
        u = pre->next;
        pre->next = u->next;
        free(u);
    }
    free(head);
}

/* 10. 将带头结点的单链表A分解为两个带头结点的单链表A和B，使得A中为奇数序号的元素，B为偶数序号元素 */
LinkList DisCreat(LinkList A){
    int i = 0;
    LNode *B, *ra = A, *rb = B, *p;     //ra和rb指向A，B的尾节点
    B->next = NULL;
    p = A->next;
    A->next = NULL;
    while(p != NULL){
        i++;
        if (i % 2 == 0){
            rb->next = p;
            rb = p;
        }
        else{
            ra->next = p;
            ra = p;
        }
        p = p->next;
    }
    ra->next = rb->next = NULL;
    return B;
}

/* 11. 在10题的基础上将B逆置，即B采用头插法 */
LinkList DisCreat(LinkList A){
    LNode *B, *ra = A, *p, *q;     //ra和rb指向A，B的尾节点
    B->next = NULL;
    p = A->next;
    A->next = NULL;
    while(p != NULL){
        ra->next = p;
        ra = p;
        p = p->next;
        if (p != NULL)
            q = p->next;
        p->next = B->next;
        B->next = p;
        p = q;
    }
    ra->next = NULL;
    return B;
}

/* 12. 去掉递增有序单链表中重复值的元素 */
void Dele_Same(LinkList &L){
    LNode *p = L->next, *q;
    if (p == NULL)  return;
    while(p->next != NULL){
        q = p->next;
        if (p->data == q->data){
            p->next = q->next;
            free(q);
        }
        else
            p = p->next;
    }
}

/* 13. 将两个递增单链表合成一个递减单链表 */
void Merge(LinkList &L1, LinkList &L2){
    LNode *r, *p1 = L1->next, *p2 = L2->next;
    L1->next = NULL;
    while (p1 && p2){
        if (p1->data <= p2->data){
            r = p1->next;
            p1->next = L1->next;
            L1->next = p1;
            p1 = r;
        }
        else{
            r = p2->next;
            p2->next = L2->next;
            L2->next = p2;
            p2 = r;
        }
    }
    if (p1) p2 = p1;
    while(p2){
        r = p2->next;
        p2->next = L1->next;
        L1->next = p2;
        p2 = r;
    }
    free(L2);
}

/* 14. 从两个递增单链表中的公共元素产生单链表C */
LinkList Get_Common(LinkList A, LinkList B){
    LNode *p = A->next, *q = B->next, *r, *s;
    LinkList C = (LinkList)malloc(sizeof(LNode));
    r = C;
    while(p && q){
        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;
}

/* 15. 两个单链表A和B递增，求交集放于A中 */
LinkList Union(LinkList A, LinkList B){
    LNode *pa, *pb, *pc, *u;
    pa = A->next;
    pb = B->next;
    pc = A;
    while(pa && pb){
        if (pa->data == pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            pb = pb->next;
            free(u);
        }
        else if(pa->data < pb->data){
            u = pa;
            pa = pa->data;
            free(u);
        }
        else{
            u = pb;
            pb = pb->next;
            free(pb);
        }
        while(pa){
            u = pa;
            pa = pa->next;
            free(u);
        }
        while(pb){
            u = pb;
            pb = pb->next; 
            free(pb);
        }
    }
    pc->next = NULL;
    free(B);
    return A;
}

/* 16. 两个单链表A和B， 判断B是否为A 的连续子序列 */
bool Pattern(LinkList A, LinkList B){
    LNode *p = A, *pre = p, *q = B;
    while(p && q){
        if (p->data == q->data){
            p = p->next;
            q = q->next;
        }
        else{
            pre = pre->next;
            p = pre;
            q = B;
        }
    } 
    if (!q) return true;
    else return false;
}

/* 17. 判断带头结点的循环双链表是否对称 */
bool symmetry(DLinkList L){
    DNode *p = L->next, *q = L->prior;
    while(p != q && q->next !=p){
        if (p->data == q->data){
            p = p->next;
            q = q->prior;
        }
        else return false;
    }
    return true;
}

/* 18. 两个循环单链表A和B，将B连接到A之后，仍保持循环链表形式 */
LinkList Link(LinkList A, LinkList B){
    LNode *p, *q;
    p = A;
    while(p->next != A)
        p = p->next;
    q = B;
    while (q->next !=B)
        q = q->next;
    p->next = B;
    q->next = A;
    return A;
}

/* 19. 重复找到带头结点的循环单链表中的最小值输出并删除，直至单链表为空再删除头结点 */
void Dele_Min(LinkList &L){
    LNode *p, *pre, *minp, *minpre;
    while(L->next != NULL){
        p = L->next;
        pre = L;
        minp = p;
        minpre = pre;
        while (p != L){
            if (p->data < minp->data){
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        printf("%d", *minp);
        minpre->next = minp->next;
        free(minp);
    }
    free(L);
}

/* 20. 对带头指针L带头结点的非循环双向链表，freq访问频度域（初值为0，每调用Locate（L,x）一次就加1），
    同时链表按freq递减排序，最近访问结点排在相同频度之前 */
DLinkList Locate(DLinkList L, int x){
    DNode *p = L->next, *q;   //q为p的前驱
    while(p && p->data != x)
        p = p->next;
    if (!p){
        printf("不存在值为x的结点\n");
        exit(0);
    }
    else{
        p->freq++;
        if (p->next != NULL)
            p->next->prior = p->prior;
        p->prior->next = p->next;
        q = p->prior;
        while(q != L && q->freq <= p->freq)
            q = q->prior;
        p->next = q->next;
        q->next->prior = p;
        p->prior = q;
        q->next = p;
    } 
    return p;
}

/* 21. 带头指针的单链表，查找链表中倒数第k个位置的结点，若查找成功，输出date域的值，并返回1， 否则只返回0*/
/* 设计思想：两个指针片p，q。p先移动k个位置后同步移动p，q */
int Search(LinkList list, int k){
    LNode *p = list->next, *q = list->next;
    int count = 0;
    while(p){
        if (count < k) count++;
        else  q = q->next;
        p = p->next;
    }
    if (count < k) return 0;
    else{
        printf("%d", q->data);
        return 1;
    }
}

/* 22. 带头结点的单链表存储单词，当两个单词有相同后缀是，可共享相同后缀的存储空间。设str1和str2分别指向
    两个单词所在单链表的头结点 ，找出str1 和 str2所指向两个链表公共后缀的起始位置*/
/* 设计思想：1.求出两表长度分别为m,n
             2.让长的那个先走|m-n|+1个节点
             3.之后同时移动两个指针，当两个指针同时指向同一地址时结束               
*/
int Length(LinkList L){
    int count = 0;
    LNode *p = L->next;
    while (p){
        count++;
        p = p->next;
    }
    return count;
}
LNode* Find_Addr(LinkList str1, LinkList str2){
    int m, n, count = 0;;
    LNode *p = str1->next, *q = str2->next;
    m = Length(str1);
    n = Length(str2);
    if (m > n)
        for (int i = 0; i < m-n+1; i++)
            str1 = str1->next;
    else
        for (int i = 0; i < n-m+1; j++)
            str2 = str2->next;
    while (str1 != str2){
        p = p->next;
        q = q->next;
    }
    return p->next;
}   
/* 时间复杂度O(len1 + len2) */

/* 23. 带头结点的单链表保存m个整数，删除绝对值相同的结点，仅保留第一次出现的结点 */
/* 设计思想：空间换时间，设置辅助数组来保存第一次出现的数 */
void Delete(LinkList &L, int n){
    LNode *p = L, *r;
    int *a;
    a = (int *)malloc(sizeof(int)*(n+1));
    memset(a, 0, sizeof(a));
    while(p->next != NULL){
        int m = abs(p->next->data);
        if (*(a+m) == 0){
            *(a+m) = 1;
            p = p->next;
        }
        else{
            r = p->next;
            p->next = r->next;
            free(r);
        }
    }
    free(a);
}
/* 时间复杂度O(m), 空间复杂度O(n) */

/* 24. 判断一个链表是否有环，如果有，找出环的入口并返回，否则返回NULL */
LNode* FindLoopStart(LNode *head){
    LNode *fast = head, *slow = head;
    while (slow != NULL && fast->next !=NULL){
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (slow == NULL || fast->next == NULL)
        return NULL;
    LNode *p1 = head, *p2 = slow;
    while(p1 != p2){
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

/* 25. 带头结点的单链表中{A1, A2, ..., An}，重新排列结点使其成为{A1, An, A2, An-1,...},
    要求空间复杂度为O(1) */
/* 设计思想：1. 后半段原地逆置，设指针p和q，p每次走一步，q每次走两步,当q到结尾时，p指向中间节点
            2.依次从前后两段各取一个结点按要求重排
 */
void Change_List(LNode *h){
    LNode *p, *q, *r, *s;
    p = q = h;
    while(q->next != NULL){
        p = p->next;
        q = q->next;
        if (q->next != NULL) q = q->next;
    }
    q = p->next;    // p指向中间节点，q指向后半段首节点
    p->next = NULL;
    while(q != NULL){
        r = q->next;
        q->next = p->next;
        p->next = q;
        q = r;
    }
    s = h->next;    //s 指向前半段第一个数据结点
    q = p->next;    //q 指向后半段第一个数据结点
    p->next = NULL;
    while(q != NULL){
        r = q->next;
        q->next = s->next;
        s->next = q;
        s = q->next;
        q = r;
    }
}