Chapter 2 linked list (2)

This article is used to record the code involved in the review of data structure, the problems encountered and the solutions

Wang Tao after class exercises

2.2 delete all nodes with the value of X and free up their space; The node with value x is not unique

void Del_x(LinkList &L, int x){
    LNode *q = L ;
    LNode *p = q->next;
    while (p){
        if (p->data==x){
            q->next = p->next;
            free(p);
            p = q->next;
            continue;
        }
        q = q->next;
        p = q->next;
    }
}

Break & continue use

Note: the difference between break and continue

break: Directly exit the cycle without starting the next cycle
continue: Exit the current cycle and start the next cycle

2.3 reverse output linked list

Idea: using stack, first in and last out, and recursive function uses recursive stack

void r_PrintLink(LinkList L){
    if(L->next)
        r_PrintLink(L->next);
    cout << L->data << " " ;
}

Note: the linked list function parameters of the leading node should be brought into L - > next, otherwise the value of the leading node will be output

2.4 delete minimum node

In addition to the following methods, you can consider setting two nodes directly and recording the minimum node each time, which is more viewable

LinkList Del_min(LinkList &L){
    LNode *q = L, *s=L;
    LNode *p = q->next;
    int x = L->next->data;
    while(p){
        if (p->data<x){
            s = q;
            x = p->data;
        }
        q = q->next;
        p = q->next;
    }
    p = s->next;
    s->next = p->next;
    free(p);
    return L;
}

2.5 reverse the single linked list, space O(1)

LinkList Reverse(LinkList &L){
    LNode *p, *q, *s ;
    p = L->next;
    s = p->next;
    q = s->next;
    p->next = NULL;
    while(q){
        s->next = p;
        p = s;
        s = q;
        q = s->next;
    }
    s->next = p;
    L->next = s;
    return L;
}

Improvement: it is equivalent to re establishing the linked list by head insertion

 LinkList h_Reverse(LinkList &L){
    LNode *p, *r;
    p = L->next;
    L->next = NULL;
    while (p) {
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
    return L;
}

Improvement: in pointer loop, while is more convenient than for

LNode *GetElem(LinkList L, int i){
    if (i<1)  return NULL;
    LNode *p;
    p = L->next;
    int j=0 ;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p;
}

2.7 delete elements between unordered tables s and t

LinkList Del_Range(LinkList &L, int s, int t){
    if (s>t) return NULL;
    LNode *p, *q;
    q = L;
    p = L->next;
    while(p){
        if (p->data<t && p->data>s){ //Delete Vertex 
            q->next = p->next;
            free(p);
        }
        q = q->next;
        p = q->next;
    }
    return L;
}

2.8 find the common node of two linked lists

The original method: the pointer p points to La, and then traverse Lb to find the same node as the node p refers to at this time
------But! High time complexity, O(len1) ✖️ len2)

Important idea: a special property of linked list

If two linked lists point to the same node in the middle, the nodes after this node of the two linked lists are the same

Improvement: just find the first common node of the two linked lists
** ⚠️: Since the first common node is equal, the number of nodes behind it is the same
-----But! La and Lb are not necessarily the same len gt h – > the first (len1-len2) of a longer linked list will certainly not have a common node

Conclusion: the long linked list is compared from (len1-len2), and both La and Lb can traverse backward at the same time < -- (the length after the common node is the same)

LinkList Search_Common(LinkList La, LinkList Lb){
    int len1 = getLength(La);
    int len2 = getLength(Lb);
    int dis;
    LinkList l, s;
    if (len1>len2){
        dis = len1 - len2 ;
        l = La->next;
        s = Lb->next;
    }
    else{
        dis = len2 - len1 ;
        l = Lb->next;
        s = La->next;
    }
    while (dis--)
        l = l->next;
    LNode *p = (LNode *)malloc(sizeof(LNode)); //Set a header node for the common node chain
    while(l){
        if (l==s){
            p->next = l;
            return p;
        }
        l = l->next;
        s = s->next;
    }
    // Add a header node to the empty table, otherwise an error will occur during printing
    p->next = NULL;
    return p;
}

2.9 increment the ordered output linked list and release the nodes

void aPrint_Del(LinkList &L){
    LNode *q, *p, *ml, *prem ;
    int min;
    while(L->next){
        q = L;
        p = L->next;
        ml = p;
        prem = q;
        min = p->data;
        while(p){
            if (p->data < min){
                ml = p;
                prem = q;
                min = p->data;
            }
            q = q->next;
            p = q->next;
        }
        cout << ml->data << " " ;
        prem->next = ml->next;
        free(ml);
    }
    cout << endl ;
}

2.10 divide the linked list into two linked lists with odd and even serial numbers respectively

LinkList split_List(LinkList &La){
    LNode *q = La;
    LNode *p = La->next;
    LinkList Lb = (LNode *)malloc(sizeof(LNode));
    Lb->next = NULL;
    LNode *rb = Lb;
    int i=1;
    while(p){
        if (i%2==0){
            q->next = p->next;
            rb->next = p;
            p->next = NULL;
            rb = p;
            p = q->next;
        }
        else{
            q = q->next;
            p = q->next;
        }
        
        i++;
    }
    return Lb;
}

2.12 delete duplicate elements in the incremental ordered linked list

//Delete duplicate elements in the incremental ordered linked list

LinkList del_Same(LinkList &L){
    LNode *q = L->next;
    LNode *p = q->next;
    while (p) {
        while (p->data==q->data){
            q->next = p->next;
            free(p);
            p = q->next;
        }
        q = q->next;
        p = q->next;
    }
    return L;
}

Merge two increasing ordered linked lists into decreasing ordered linked lists

Idea: using the head interpolation method, first insert the smaller node into L

LinkList MergeList(LinkList &La, LinkList &Lb){
    LinkList L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *a, *b, *p;
    a = La->next;
    b = Lb->next;
    La->next = NULL;
    Lb->next = NULL;
    while (a && b){
        if(a->data < b->data){
            p = a;
            a = a->next;
        }
        else{
            p = b;
            b = b->next;
        }
        p->next = L->next;
        L->next = p ;
    }
    while (a){ //If a has more, insert it into the linked list
        p = a;
        a = a->next;
        p->next = L->next;
        L->next = p;
    }
    while (b){ //If b has any remaining, insert it into the linked list
        p = b;
        b = b->next;
        p->next = L->next;
        L->next = p;
    }
    return L;
}

2.14 find the common element list Lc in the incremental ordered linked lists La and Lb

Note the distinction between and public nodes
The common element only needs the data of two nodes to be equal, and it does not need to be the same address in memory

LinkList get_Common(LinkList La, LinkList Lb){
    LinkList Lc = (LNode *)malloc(sizeof(LNode));
    Lc->next = NULL;
    LNode *cr = Lc;
    LNode *pa = La->next;
    LNode *pb = Lb->next;
    LNode *s;
    int x = 0;
    while(pa && pb){
        while (pa->data < pb->data && pa)
            pa = pa->next;
        while (pa->data > pb->data && pb) {
            pb = pb->next;
        }
        if (pa->data==pb->data && pa && pb)
            if (pa->data != x){//Avoid duplicate elements
                x = pa->data;
                s = (LNode *)malloc(sizeof(LNode));
                s->data = x;
                s->next = cr->next;
                cr->next = s;
                cr = s;
            }
        pa = pa->next;
        pb = pb->next;
    }
    return Lc;   
}

2.16 judge whether B is a subsequence of A

bool Pattern(LinkList La, LinkList Lb){
    LNode *pa = La->next;
    LNode *pb = Lb->next;
    while(pb && pa){
        while (pa->data != pb->data){
            pa = pa->next;
            if(!pa) return false; //If La cannot find the same node as Lb, it must not be a subsequence
        }
        pa = pa->next;
        pb = pb->next;
        if (pa==NULL && pb!=NULL) return false;
    }
    return true ;
}

2.17 judge whether the circular double linked list is symmetrical

Data structure of circular double linked list

Circular double linked list node

typedef struct rLNode{ //Define node
    int data;
    struct rLNode *prior, *next;
}rLNode, *rLinkList;

Creation of circular double linked list

rLinkList Creat_rList(rLinkList &L, int n, int *E){
    L = (rLNode*)malloc(sizeof(rLNode));
    rLNode *p, *s ;
    p = L;
    for(int i=0; i<n; i++){
        s = (rLNode*)malloc(sizeof(rLNode));
        s->data = E[i];
        s->prior = p;
        p->next = s;
        p = s;
    }
    p->next = L;
    L->prior = p;
    return L;
}

Print circular double linked list

void Print_rList(rLinkList L){
    rLNode *p=L;
    while (p->next != L){
        p = p->next;
        cout << p->data << " ";
    }
    cout << endl;
}

Judge whether the circular double linked list is symmetrical (leading node)

//Scan from front to back
bool r_Symmetry(rLinkList rL){
    rLNode *h = rL->next;
    rLNode *t = rL->prior;
    while(h!=t && t->next!=h){
        if (h->data != t->data)
            return false;
        h = h->next;
        t = t->prior;
    }
    return true;
}

2.18 merge circular single linked list (Lb after La)

First write an output function of circular single linked list

void r_PrintList(LinkList L){
    LNode *p=L;
    while (p->next != L){
        p = p->next;
        cout << p->data << " ";
    }
    cout << endl;
}

Create circular single linked list

p -> next = L; //Only difference

Merge circular single linked list (Lb after La)

LinkList r_Link(LinkList &La, LinkList &Lb){
    LNode *ra=La, *rb=Lb;
    while(ra->next != La)
        ra = ra->next;
    while(rb->next != Lb)
        rb = rb->next;
    ra->next = Lb->next;
    rb->next = La;
    Lb->next = NULL;
    return La;
}