Linear table – problem set

Today’s main share is the idea of solving the problem, I hope to help you. No matter what kind of exercises, should first think about the way to solve the problem, so that the problem will get twice the result with half the effort. 😝.

The first problem is to merge two increasing ordered lists into a list of ordered lists; Requires that the resulting linked list still uses the storage space of two linked lists and does not take up additional storage space. No duplicate data is allowed in the table

First let’s think about the idea (just to give you an idea of how to solve the problem, or maybe there’s a better idea).

1. Suppose there are two ordered linked lists La, Lb. (respectively: {1,2,4},{2,3,4}, our purpose is to become {1,2,3,4}) 2. We can declare a header pointer Lc (borrowed from La), Pa, and Pb to point to elements in La and Lb, respectively. Loop through, Lc stores the smaller, then equal, pa, delete Pb. 4. Reach the end of one of the elements and concatenate the remaining elements directly (because this is an ordered increment) 5. The Lb was finally released.Copy the code

Then go straight to the code:

void mergeLinkList(ListNode *La, ListNode *Lb, ListNode *Lc){
   ListNode pa,pb,pc,temp;
   pa = (*La)->next;
   pb = (*Lb)->next;
   
   *Lc = pc = (*La);
   
   while (pa && pb) {
       
       if (pa->data < pb->data) {
           pc->next = pa;
           pc = pa ;
           pa = pa->next;
       }else if (pa->data > pb->data){
           pc->next = pb;
           pc = pb;
           pb = pb->next;
       }else{ temp = pb; pc->next = pa; pc = pa ; pa = pa->next; pb = temp->next; free(temp); } } pc->next = pa? pa:pb; free(*Lb); }Copy the code

Problem 2: Given that two linked lists A and B represent two sets respectively. Its elements are incrementally arranged in columns. Design an algorithm for finding the intersection of A and B, and store it in A linked list; For example: La = {2,4,6,8}; ,6,8,10 Lb = {4}; ,6,8 Lc = {4}

As usual, this time to think about their own ideas:

This is actually similar to the first problem. 1. Similarly,La,Lb, lc. pa, Pb, PC, then Lc borrows La's header 2. If pa is less than Pb, pa moves backwards, and then the previous node is deleted. 4. If Pa is greater than Pb, Pb will move backwards and then delete the previous node. 5. Reach the end of one and delete the end of the other as there is no more pain. Release the LbCopy the code

The code:

void intersectionLinkList(ListNode *La, ListNode *Lb, ListNode *Lc){
    ListNode pa,pb,pc,temp;
    pa = (*La)->next;
    pb = (*Lb)->next;
    *Lc = pc = (*La);
    
    while (pa && pb) {
        if (pa->data < pb->data) {
            temp = pa;
            pa = pa->next;
            free(temp);
        }else if (pa->data>pb->data){
            temp = pb;
            pb = pb->next;
            free(temp);
        }else{ pc->next = pa; pc = pa; pa= pa->next; temp = pb; pb = pb->next; free(temp); }} //Lb is empty, delete all elements in the non-empty table Lawhile(pa) { temp = pa; pa = pa->next; free(temp); } // if La is empty, delete all elements from non-empty table Lbwhile (pb) {
        temp = pb;
        pb = pb->next;
        free(temp);
    }
    pc->next = NULL;
    free(*Lb);
}
Copy the code

Third problem: design an algorithm to “rotate” the link directions of all nodes in the linked list, that is, only use the storage space of the original table. In other words, the space complexity of the algorithm is O(1). For example :L={0,2,4,6,8,10}, reversed :L={10,8,6,4,2,0};

Ideas:

1. Head insertion immediately comes to mind. 2. Then go back and forthCopy the code

This is the direct code (after reading the big call simple 😄) :

void rotateLinkList(ListNode *La){
    
    ListNode p,q;
    p = (*La)->next;
    (*La)->next = NULL;
    
    while(p) { q = p->next; p->next = (*La)->next; (*La)->next = p; p = q; }}Copy the code

Design an algorithm to delete all elements in an incrementally ordered list whose values are greater than or equal to mink and less than or equal to maxk(mink is a given parameter whose values may be the same as or not different from the elements in the list).

Guys, the idea:

1. First he will give 2 values. 2. We eliminate the nodes between mink and maxk. 3. Use mink to point to maxkCopy the code

The code:

void deleteItems(ListNode *La,int mink, int maxk){ ListNode p,q,pre,temp; pre = (*La); p= (*La)->next; // find the previous nodewhile(p && p->data < mink) { pre = p; p = p->next; } // find the next nodewhile(p && p->data <= maxk) { p = p->next; } // save a wave and point to the past q = pre->next; pre->next = p; // delete the middle nodewhile (q!=p) {
        temp = q->next;
        free(q);
        q = temp;
    }
}
Copy the code

Fifth problem: Suppose n(n>1) integers are stored in a one-dimensional array R, and try to design an algorithm that is as efficient as possible in both time and space. The sequence column saved in R is moved to the left by p positions (0< P <n), that is, the data in R is changed from (x0,x1,…… ,xn-1) transforms to (xp, XP +1… ,xn-1,x0,x1,… , xp – 1). For example: the pre [10] =,1,2,3,4,5,6,7,8,9 {0}, n = 10, p = 3; The pre [10] =,4,5,6,7,8,9,0,1,2 {3}.

Don’t panic when you see the long question, most of this question is an example, and then let you understand what he wants to express. (All he wants to say is move to the left.)

Ideas:

1. Invert all elements of a one-dimensional array. 2. Locate the location of n-p-1 and divide it into two arrays. 3. In the inverse (of course, you may have a better way. Try more. I should write the simplest. 😄)Copy the code

Code:

Void Reverse(int *arr, int left, int right){int temp;while(left < right) { temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left ++; right --; }} void leftMove(int *arr, int n, int p){// Reverse(arr, 0, n-1); // Reverse(arr, 0, n-p-1); // Reverse(arr, n-p, n-1); }Copy the code

Given an integer sequence A = (a0, A1,a2… An-1), where (0<= ai <=n),(0<= I <=n). If ap1= AP2 =… =apm = x, and m>n/2(0<= PK <n,1<=k<=m), then x is called the principal element of A. For example, if A = (0,5,5,3,5,7,5,5), then 5 is the primary element; If B = (0,5,5,3,5,1,5,7), then there is no principal element in A. Suppose that n elements in A are stored in A one-dimensional array, please devise an algorithm as efficient as possible to find the principal element in the array element. If there is A principal element, the element will be output, otherwise -1 will be output.

This problem is still so long, do not panic, slowly analysis.

Find primary elements in array (number > Number of arrays /2)Copy the code
1. First temporarily select key as a primary element. Iterate over the number set. If the same number is found, count is increased by one, otherwise it is decreased by one. 2. When count is less than 0, replace the next element as the candidate primary element. 3. Traversal does not mean that the key is the main element. Count >n/2; count>n/2;Copy the code

The code:

int findMianElement(int *A, int n){
    int key = A[0];
    int count = 1;
    for (int i = 0; i<n; i++) {
        
        if (A[i] == key) {
            count ++;
        }else{
            if (count > 0 ) {
                count --;
            }else{ key = A[i]; count = 1; }}}if (count > 0) {
        for (int i = count = 0; i<n; i++) {
            if(key == A[i]) { count ++ ; }}}if (count >n/2) {
        return key;
    }
    return- 1; }Copy the code

Question 7: use singly linked lists to save m integers, node structure (data link), and | data | < = n (n is positive integer). Now it’s time to design an algorithm with as high a time complexity as possible. For the nodes in the linked list whose data has the same absolute value, only the nodes that appear for the first time are retained, and the remaining nodes with the same absolute value are deleted. For example, if the linked list A={21,-15, 15,-7,15}, the deleted linked list A={21,-15,-7};

Suggest an algorithm that is as efficient as possible in time complexity. So we can trade space for time.Copy the code

Ideas:

1. Apply for an auxiliary array greater than n. The initial value is 0. 2. Iterate through the list. Assign the array (with the absolute value removed, of course) to a value that is assigned to 1. 3. If the value is 1, it is not the first occurrence, and delete. 4. If this value equals 0, it indicates the first occurrence, leave.Copy the code

The code:

void deleteEqualABSValue(ListNode *L,int n){ int *p = alloca(sizeof(int)*n); ListNode r = *L; //2. The initial value of the array element is nullfor(int i = 0; i < n; i++) { *(p+i) = 0; } ListNode temp = (*L)->next; //4. Iterate through the list until temp = NULL;while(temp! = NULL) {//5. If the absolute value already exists on the node, delete the nodeif(p/abs (temp - > data) = = 1) {/ / temporary pointer to temp - > next r - > next = temp - > next; // Delete the node to which temp points free(temp); Temp = r->next; }else{//6. If the node does not appear, set the corresponding position in the array to 1; p[abs(temp->data)] = 1; r = temp; Temp = temp->next; }}}Copy the code

conclusion

In fact, parsing all problems is the same, first clear ideas, and then write logic according to the ideas. No one wants to write anything directly at first sight (unless they have memorized the problem). . So it’s super important to figure out how to do it.