Title 1:

Merge two increasing ordered lists into one ordered list; Requires that the resulting linked list still uses the storage space of both lists and does not take up additional storage space. No duplicate data is allowed in the table

Key words:

  • Incrementally ordered linked lists
  • Duplicate data is not allowed
  • Preserving the increasing relation (post-interpolation)
  • No extra storage means that no new nodes are created and the values are assigned to the linked list

Algorithm idea:

(1) Assume that the linked lists to be merged are La and Lb, and the new table after merging uses the header pointer Lc(the table header node of Lc is set as the table header node of La) to point to. Pa and Pb are working Pointers of La and Lb respectively. (2) Starting from the initial node, (3) If the elements in the two lists are equal, only the elements in La and Lb are selected, and the elements in Lb are deleted, so as to ensure that there are no duplicated elements in the list after merging. (4) When an expression to the end of the table is empty, the remaining elements of the non-empty table are directly linked to the end of the Lc table. (5) Finally release the head of the linked list Lb.

code

Void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc){// Merge two incremental ordered lists La,Lb into one incremental ordered list Lc LinkList PA, Pb, PC,temp; // Merge two incremental ordered lists La,Lb into one incremental ordered list Lc LinkList PA, Pb, PC,temp; //pa is a working pointer to La,pb is a working pointer to Lb, initialized as the initial node; pa = (*La)->next; pb = (*Lb)->next; *Lc = pc = *La; //Lc uses the first node of La and the PC as the fingerprint of the new nodewhile(pa &&pb) {// Because the original list is ordered, when a list ends, the next list can be directly linked to the new b listif(pa->data < pb->data) {pa-> next = pa; pa-> next = pa; // Add small elements to Lc list pa PC = pa; Pa = pa->next; // Since pa is already linked to Lc, change pa to the next node of PA}else if(pa->data > pb->data){pa-> next = pb->data; pc = pb; pb = pb->next; }else{// select the element in La and delete the element in Lb; pc->next = pa; pc = pa; Pa = pa ->next; Temp = pb->next; temp = pb->next; Pb ->next free(pb); pb->next free(pb); Pb = temp; // assign temporary pb->next to pb}} // link the remaining elements of the non-empty table at the end of Lc table PC ->next = pa? pa:pb; // free the Lb header free(*Lb); }Copy the code

Topic 2:

We have two linked lists A and B representing two sets. Its elements are arranged incrementally. 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}

Key words:

Pick the equal elements in the two tables in turn and link again, delete the other unequal elements;

Algorithm idea:

  • (1) Assume that the linked lists to be merged are La and Lb, and the new table after merging uses the header pointer Lc(the table header node of Lc is set as the table header node of La) to point to. Pa and Pb are working Pointers of La and Lb respectively. Initialize to the leading node of the corresponding linked list
  • (2) Starting from the initial node, when the two linked lists La and Lb do not reach the end node of the list.
  • (3) If the elements in two tables are equal, only the elements in La table are extracted and the elements in Lb table are deleted;
  • (4) If the element in one of the tables is smaller, delete the smaller element in the table. The working pointer of this table moves back;
  • (5) When one of the linked lists La and Lb reaches the end of the list first and the end node is empty, all the elements in the other non-empty list are deleted successively, and finally the linked list Lb is released;

Code:

Void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc){void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc); LinkList pa,pb,pc,temp; //pa is a working pointer to La,pb is a working pointer to Lb, initialized as the initial node; The header of La is the header of Lc; pa = (*La)->next; pb = (*Lb)->next; *Lc = pc = *La;while (pa && pb) {
        
        if(pa->data == pb->data) { //(1). Connect pa to PC,pa pointer back; pc->next = pa; pc = pa; pa = pa->next; //(2) delete temp = pb from Lb; pb = pb->next; free(temp); }else if(pa->data < pb->data){// delete the element with the lower value La; temp = pa; pa = pa->next; free(temp); }else{// delete the element temp = pb from Lb; 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

Title 3:

Design an algorithm that “rotates” the link directions of all nodes in a linked list, requiring only 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};

Key words:

  • Can’t open up a new space, can only change the point of the pointer;
  • It can be considered to extract nodes one by one, using the idea of creating a linked list with the method of forward insertion, and insert nodes after the first node at a time.
  • Because the node inserted first is the end of the table, and the node inserted later is the head of the table, the reversal of the linked list can be realized.

Algorithm idea:

  • (1) The original head node *L is used,p is the working pointer, and p points to the head node at the beginning. Because the extracted nodes are inserted forward in turn, the pointer field of the head node is initially null to ensure that the tail of the linked list is empty.
  • (2) The linked list is traversed from front to back, and the nodes are selected in turn. Before the nodes are selected, the pointer Q should be used to record the successor nodes to prevent the loss of the successor nodes after linking;
  • (3) After the extracted node is inserted into the head node, the last P points to the new node to be processed q(p=q);

Code:

Inverse(LinkList *L){// Purpose: invert the single linked list; LinkList p,temp; // Set p to the head node because next is null; p = (*L)->next; (*L)->next = NULL; // Iterate over the listwhile(p! P ->next temp = p->next; P ->next = (*L)->next; p->next = (*L)->next; //*p inserted after the header; (*L)->next = p; P = temp; }}Copy the code

Topic 4:

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 can be the same or different from the elements in the list);

Key words:

  • By traversing the list, you can locate the lower and upper boundaries of the deleted elements,
  • The node whose first value is greater than mink and the node whose first value is greater than or equal to maxk can be found.

Algorithm idea:

  • (1) Find the first node whose value is greater than mink, and use Q to point to this node and pre to point to its precursor node;
  • (2) Continue to traverse the linked list, find the node whose first value is greater than or equal to maxk, and point to this node with P;
  • (3) Modify the pointer field of the lower boundary precursor node so that it points to the upper boundary (pre->next = p);
  • (4) Release the space of nodes to be deleted successively (all nodes between pre and P);

Code:

void DeleteMinLinkList p,q,pre; Max(LinkList *L, int mink, int maxk){LinkList p,q,pre; pre = *L; LinkList temp; P = (*L)->next; P ->data < mink, pre points to the node before P, i.e., all nodes before pred are less than minkwhile(p && p->data < mink) {pre = p; p = p->next; } //2. Find the first node whose value is greater than or equal to maxkwhile(p && p->data<=maxk) { p = p->next; Q = pre->next; q = pre->next; pre->next = p; // Then release all stages before pre and pwhile (q != p) {
        temp = q->next;
        free(q);
        q = temp;
    }
}
Copy the code

Title 5:

Let n(n>1) integers be 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 saved in R is cyclically shifted 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}

Algorithm idea:

    1. First, invert n data in situ 9,8,7,6,5,4,3,2,1,0;
    1. Disassemble n data into [9,8,7,6,5,4,3] [2,1,0]
    1. The first n-P data and the last P data were inverted in situ respectively. ,4,5,6,7,8,9 [3] [0]

Code:

Void Reverse(int *pre,int left, int right){void Reverse(int *pre,int left, int right){void Reverse(int *pre,int left, int right); int i = left,j = right; int temp; // Swap pre[I] and pre[j] valueswhile(I < j) {// Exchange temp = pre[I]; pre[i] = pre[j]; pre[j] = temp; // I moves right,j moves left I ++; j--; }}Copy the code

Complexity analysis:

Time complexity: O(n); Space complexity :O(1);

Topic 6:

Given A sequence of integers 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), 5 is the primary element; If B = (0,5,5,3,5,1,5,7), then there is no principal element in A. Suppose n elements in A are stored in A one-dimensional array, please design an algorithm as efficient as possible to find the principal element in the array element. If there is A principal element, the element is output, otherwise -1 is output.

Analysis of the topic:

Given A sequence of integers 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), 5 is the primary element; If B = (0,5,5,3,5,1,5,7), then there is no principal element in A. Suppose n elements in A are stored in A one-dimensional array, please design an algorithm as efficient as possible to find the principal element in the array element. If there is A principal element, the element is output, otherwise -1 is output.

Algorithm idea:

    1. Select the candidate primary element and scan each integer in the array from front to back, assuming the first integer is the primary element and storing it in Key with a count of 1. If the next integer is still equal to key, the count is increased by 1. Otherwise, the count is decreased by 1. When the count is reduced to 0, the next integer encountered is saved to the key and the count is rewritten as 1. Start a new count. You can repeat the above process from the current position until all array elements have been scanned;
    1. Determine whether the element in key is the real main element, scan the array again, count the number of occurrences of the element in key, if greater than N /2, it is the main element, otherwise, there is no main element in the sequence;

Code:

Int MainElement(int *A, int n){// Int count = 1; A[0] int key = A[0]; //(1) scan array, select candidate primary elementfor(int i = 1; i < n; I ++) {//(2) if A[I] element == key, then the count of candidate primary elements is increased by 1;if (A[i] == key) {
            count++;
        }else{//(3) the current element A[I] is not A candidate primary element, count minus 1;if(count >0){
                count--;
                
            }else{//(4) if count = 0, count key = A[I]; count = 1; }} // If count >0if(count >0){//(5) Count the actual occurrences of candidate primary elementsfor (int i = count = 0; i < n; i++)
            if(A[i] == key) count++; } //(6) check if count>n/2 is the primary elementif (count > n/2) return key;
    else return- 1; // There is no primary element}Copy the code

Algorithm analysis:

Time complexity: O(n) Space complexity: O(1)

Title 7,

Used 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 that’s as efficient as possible. For 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, linked list A={21,-15, 15,-7,15}, deleted linked list A={21,-15,-7};

Analysis of the topic:

  • Asked to design a efficient algorithm as far as possible, time complexity and the known | data | < = n, so can consider to use the method of space in time.
  • Apply for an auxiliary array of size N +1(not used by cell 0).
  • Save values that have appeared in the linked list and delete them through a scan of the linked list.

Algorithm idea:

    1. Apply for auxiliary array t of size n+1 and assign initial value 0;
    1. From first finally began to traverse the list, in turn, check t [| data |] value, if [| data |] 0, namely node for the first time, keep the node, and t [| data |] = 1, if t [| data |] is not zero, then the node is removed from the list.

Code:

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

Complexity analysis:

Complexity analysis: Time complexity: O(m). If the length of the linked list is traversed once, the algorithm’s time complexity is O(m). Spatial complexity: O(n), n is the largest absolute value in the linked list