1. Merge ordered linked lists
Merge two incrementally 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 】 Incrementing ordered linked list, no repeated data is allowed, retain the incrementing relation (post-interpolation method) does not occupy extra storage space refers to that no new nodes can be opened, assigned values in the linked list;
/* Algorithm idea: (1) Assume that the linked lists to be merged are La and Lb, and the new table to be merged uses the header pointer Lc(the table header of Lc is set as the table header of La, "by using the") 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 a table reaches the end of the table, 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. */ void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc){ LinkList pa,pb,pc; Pa = (*La)->next; pb = (*Lb)->next; La PC = (*Lc) = (*La); // run through two known lists until the end of one of themwhile(pa &&pb) {// If the pa value of La is small, then the output Lc's tail PC points to PAif(pa->data < pb->data) {// use PC ->next instead of PC = pa, PC ->next = PA; // next = PC ->next; // pa = pa->next; }else if(pa->data > pb->data) {// next = pb; pc = pc->next; pb = pb->next; }else if(pa->data == pb->data) {// pa-> next = pa; pc = pc->next; pa = pa->next; LinkList temp = pb; LinkList temp = pb; pb = pb->next; free(temp); }} // abovewhileAfter traversal, there may be non-empty table elements left untraversed, in this case, these elements should be directly linked at the end of Lc table PC ->next = pa? pa : pb; // Release the Lb header pointer free(*Lb); }Copy the code2. Intersection of ordered linked lists
We know that two linked lists A and B represent two sets respectively. 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 】 Extract the equal elements in two tables and link them 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 to be merged uses the header pointer Lc(the table header of Lc is set to La) to point to. Pa and Pb are working Pointers of La and Lb respectively. (3) If the elements in the two lists are equal, only the elements in THE La table are selected and the elements in the Lb table are deleted; (4) if the elements in the La table are equal, the elements in the 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; */ void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc){// Void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc); LinkList pa,pb,pc,temp; pa = (*La)->next; pb = (*Lb)->next; pc = (*Lc) = (*La);while (pa && pb) {
if(pa->data == pb->data) { Take one, delete the other. //(1). Connect pa to PC,pa pointer back; pc->next = pa; pc = pc->next; pa = pa->next; //(2) delete temp = pb from Lb; pb = pb->next; free(temp); }else if(pa->data < pb->data) {temp = pa; pa = pa->next; free(temp); }else{ 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 code3. List reversal
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}; ,2,0,6,8,10,0,4,6,8,10 {2} – > {4} – > {6,4,2,0,8,10} – >,6,4,2,0,10 {8} – > {10,8,6,4,2,0}
【 Key words 】 Head insertion, reverse linked list. 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.
(1) Use the original head node *L,p is the working pointer,p points to the initial 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); */ void Inverse(LinkList *L){ LinkList p = (*L)->next; // next = NULL; // Continuously move the traversal node p to the front of the head node, i.e. the old head node is continuously moved back, like a hingewhile(p ! LinkList temp = p->next; P ->next = (*L)->next; // next = p; // next = p; // retrieve the successor of p p = temp; }}Copy the code4. Delete the range specified in the ordered list
【题 干 】 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.
【 Key words 】 The lower and upper boundaries of deleted elements can be located by traversing the linked list. 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, use Q to point to this node, and pre to point to the precursor node of this 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); */ void DeleteMinLinkList p,q,pre; Max(LinkList *L, int mink, int maxk){LinkList p,q,pre; pre = *L; LinkList temp; P = (*L)->next; //1. Find the node whose first value is greater 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; } //3. Q = pre->next; pre->next = p;while (q != p) {
temp = q->next;
free(q);
q = temp;
}
}
Copy the code5. Ordered lists specify range swapping
Let n(n>1) integers be stored in a one-dimensional array R. 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}
/* Select * from n; /* select * from n; 2. Disassemble n data into [9,8,7,6,5,4,3] [2,1,0] 2. The first n-P data and the last P data were inverted in situ respectively. [3,4,5,6,7,8,9] complexity analysis: time complexity: O(n); Time complexity :O(1); Void Reverse(int *pre,int left, int right){// I = left,j = right; int i = left; int j = right; int temp; // Swap pre[I] and pre[j] valueswhile(i < j) { temp = pre[i]; pre[i] = pre[j]; pre[j] = temp; // I moves right,j moves left I ++; j--; Void LeftShift(int *pre, int n, int p) {// Boundary conditionsif(p>0 &&p <n) {//1. Reverse all elements in the array (pre, 0, n-1); //2. Reverse the first n-p data (pre, 0, n-p-1); //3. Reverse the last P data (pre, n-p, n-1); }}Copy the code6. Find the array main element
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.
A primary element is an element that occurs more than half the time in an array. When there are primary elements in the array, the sum of all non-primary elements must be less than half. If you pair a primary element with a non-primary element, the last extra element that has no match is the primary element.
/* Select the candidate primary element, scan each integer in array from front to back, assume that the first integer is the primary element, store it in Key, count 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; 2. Determine whether the element in key is the real primary element, scan the array again, count the number of occurrences of the element in key, if greater than N /2, it is the primary element, otherwise, there is no primary element in the sequence; Algorithm analysis: Time complexity: O(n) Space complexity: Int MainElement(int *A, int n){int MainElement(int *A, int n){int MainElement(int *A, int n); Int key = A[0]; // Get the candidate primary element (not necessarily the element that appears the most frequently, depending on the order, of course, the primary element is independent of the order)for (int i = 1; i < n; i++) {
if(key == A[I]) {// If the element traversed == candidate primary element, count+ 1; }else{// Otherwise count -1if (count > 0) {
count--;
} elseKey = A[I]; key = A[I]; count = 1; }}} // Get the number of occurrences of candidate primary elementsif(count >0) {// If count>0, get the number of occurrencesfor(int i = count = 0; i < n; I++) {// count is not the count, but the number of occurrencesif(key == A[i]) { count++; }}} // Select the primary element and its occurrence timesif (count > n/2) {
return key;
} else {
return -1;
}
}
Copy the code7. Single linked list deweighting
[title] 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 required 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.
/* Select array t with size n+1 and set initial value to 0; 2. Start from the first finally point traverse the list and check in order t [| data |] value, if [| data |] 0, namely node for the first time, keep the node, and t [| data |] = 1, if t [| data |] not to 0, then the node is removed from the list. Complexity analysis: Time complexity: O(m). If the length of the linked list is traversed once, the algorithm's time complexity is O(m). O(n) */ void DeleteEqualNode(LinkList *L,int n){int *arr = malloc(sizeof(int)*n); // alloca // Array element initial value is nullfor(int i = 0; i < n; i++) { *(arr + i) = 0; } // pre is used to save the pre-drive of the node to be deleted. LinkList temp = (*L)->next; // Iterate through the list until temp = NULL;while(temp ! = NULL) {if(arr[abs(temp->data)] == 0) {arr[abs(temp->data)] == 0) {arr[abs(temp->data)] == 0; arr[abs(temp->data)] = 1; Pre = temp; Temp = temp -> next; }elsePre ->next = temp->next; // Delete the node free(temp); Temp = temp->next; }}}Copy the code