Data structure and algorithm (1) linear table implementation

Data structure and algorithm (2) unidirectional circular linked list creation insert delete implementation

Data structure and algorithm (3) Implementation of bidirectional linked list and bidirectional cyclic linked list

Data structures and algorithms (4) Linked list related interview questions

Data structures and algorithms (5) Stack and queue operation and implementation

Data structures and algorithms (6) The operation and implementation of queues

Data structure and algorithm (5) stack and queue operation and implementation

@TOC

1. Data structure and algorithm (4) Linked list related interview questions

Download this blog Demo: Click here to download the Demo

1.1 Linked list algorithm details

1.1.1 Merge two ordered lists

Topic 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.

For example: La{1,2,3}, Lb{3,6,9} merged into Lc {1,2,3,6,9}

Let’s analyze and solve the problem:

Analyze the problem firstThe keyword, find out the details:keywords:

Incremental ordered list, no duplicate data allowed, keep incremental relationship (post-interpolation)

No extra storage space means that no new nodes can be opened and assigned to the linked list;

Analyze the problem and list the solution ideas:

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, the smaller value is successively extracted and re-listed at the end of Lc.

(3) If the elements in the two tables are equal, only the elements in the La table are selected and the elements in the Lb table are deleted to ensure that there are no duplicate elements in the table 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 node of linked list Lb;

Problem solving and code implementation:

// Objective: To merge two increasing ordered lists La and Lb into one increasing ordered list Lc
void mergeList(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;
    pa = (*La)->next;
    pb = (*Lb)->next;
    
    *Lc = pc = *La;
    while (pa && pb) {
        if (pa->data < pb->data) {
            // Take the element in the smaller La, link pa after PC, move pa pointer back
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else if (pa->data > pb->data) {
            // take the element of the smaller Lb, link pb behind PC, and move pb pointer back
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        } else {
            // select * from La; delete * from Lb;pc->next = pa; pc = pa; pa = pa->next; temp = pb->next; free(pb); pb = temp; }}// Link the remaining elements of the non-empty table at the end of the Lc table
    pc->next = pa ? pa : pb;
    // Release the Lb header
    free(*Lb);
}
Copy the code

Time complexity:

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

Test verification:

void test1() {
    printf("Test mergeList: \n");
    
    KStatus iStatus;
    LinkList La.Lb.Lc;
    initList(&La);
    initList(&Lb);
    
    printf(Title 1: "* * * * * * * * * * * * * * \ n");
    // Design 2 incremental lists La,Lb
    for(int j = 10; j>=0; j-=2)
    {
        iStatus = insertElement(&La.1, j);
    }
    printf("La:\n");
    traverseList(La);

    for(int j = 11; j>0; j-=2)
    {
        iStatus = insertElement(&Lb.1, j);
    }
    printf("Lb:\n");
    traverseList(Lb);

    mergeList(&La, &Lb, &Lc);
    printf("Lc:\n");
    traverseList(Lc);
}
Copy the code

Output result:

Test mergeList :****** title 1:******** La: 0 2 4 6 8 10 Lb: 1 3 5 7 9 11 Lc: 0 1 2 3 4 5 6 7 8 9 10 11Copy the code

1.1.2 Find the intersection of two ordered linked lists

Question 2: Given that two linked lists A and B represent two sets, respectively, whose element addresses are arranged. Design an algorithm to find the intersection of A and B and store it in A linked list of A.

For example: La{2,4,6,8}, Lb{4,6,8} intersection Lc {4,6,8}

Let’s analyze and solve the problem:

Analyze the problem firstThe keyword, find out the details:keywords:

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

Analyze the problem and list the solution ideas:

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;

Problem solving and code implementation:

// Objective: To find the intersection of two incremental ordered lists La and Lb, using the head pointer Lc to point back;
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) {
            // The intersection is merged into the result list;
            //(1). Connect pa to PC,pa pointer back;
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            //(2) delete the corresponding elements in Lb
            temp = pb;
            pb = pb->next;
            free(temp);
        } else if (pa->data < pb->data){
            // Remove the element with the lower value La;
            temp = pa;
            pa = pa->next;
            free(temp);
        } else {
            // Delete elements with smaller Lb values;temp = pb; pb = pb->next; free(temp); }}// delete all elements in La that are not empty
    while (pa) {
        temp = pa;
        pa = pa->next;
        free(temp);
    }
    // if La is empty, delete all elements from non-empty table Lb
    while (pb) {
        temp = pb;
        pb = pb->next;
        free(temp);
    }
    //Lc terminator is null
    pc->next = NULL;
    // Release the Lb header
    free(*Lb);
}
Copy the code

Time complexity:

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

Test verification:

void test2() {
    printf("Test intersection: \n");
    
    LinkList La.Lb.Lc;
    initList(&La);
    initList(&Lb);
    printf(Topic 2: "* * * * * * * * * * * * * * \ n");
    insertElement(&La.1.8);
    insertElement(&La.1.6);
    insertElement(&La.1.4);
    insertElement(&La.1.2);
    printf("La:\n");
    traverseList(La);


    insertElement(&Lb.1.10);
    insertElement(&Lb.1.8);
    insertElement(&Lb.1.6);
    insertElement(&Lb.1.4);
    printf("Lb:\n");
    traverseList(Lb);

    intersection(&La, &Lb, &Lc);
    printf("Lc:\n");
    traverseList(Lc);
}
Copy the code

Output result:

Test intersection :****** Topic 2:******** La: 2 4 6 8 Lb: 4 6 8 10 Lc: 4 6 8Copy the code

Reverse an ordered linked list

Topic 3: Design an algorithm to rotate the link directions of all nodes in the linked list in situ, that is, only the storage space of the original table is required, in other words, the algorithm space complexity is O(1).

For example: La{0,2,4,6,8,10}, reversed: Lc {10,8,6,4,2,0};

Let’s analyze and solve the problem:

Analyze the problem firstThe keyword, find out the details:keywords:

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.

Analyze the problem and list the solution ideas:

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);

Problem solving and code implementation:

// reverse a single linked list;
void inverse(LinkList *L) {
    LinkList p,q;
    //p points to the head node;
    p = (*L)->next;
    // The pointer field of the header is null
    (*L)->next = NULL;
    while (p) {
        //q refers to the successor of p, which is used to store the next node to be inserted, otherwise the list will break and no subsequent elements will be found
        q = p->next;
        
        //*p inserted after the header;
        p->next = (*L)->next;
        (*L)->next = p;
        
        // process the next nodep = q; }}Copy the code

Time complexity:

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

Test verification:

void test3() {
    printf("Test intersection: \n");
    
    KStatus iStatus;
    LinkList La.Lb.L;
    initList(&La);
    initList(&Lb);
    
    printf(Title 3: "* * * * * * * * * * * * * * \ n");
    initList(&L);
    for(int j = 10; j>=0; j-=2)
    {
        iStatus = insertElement(&L.1, j);
    }
    printf("Before L reversal :\n");
    traverseList(L);

    inverse(&L);
    printf("After L reversal :\n");
    traverseList(L);
}

Copy the code

Output result:

Test intersection :****** Title 3:******** L before reversal: 0 2 4 6 8 10 L after reversal: 10 8 6 4 2 0Copy the code

1.1.4 Delete certain conditional elements

Problem 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 those of the elements in the list).

Let’s analyze and solve the problem:

Analyze the problem firstThe keyword, find out the details:keywords:

By traversing the linked list, the lower and upper boundaries of deleted elements can be located. 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.

Analyze the problem and list the solution ideas:

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);

Problem solving and code implementation:

Delete all elements in incrementally ordered list L whose values are greater than or equal to mink and less than or equal to maxk
void deleteMinMax(LinkList *L, int mink, int maxk) {
    LinkList p, q, pre,temp;
    pre = *L;
    //p points to the head node
    p = (*L)->next;
    
    //1. Find the node whose first value is greater than mink
    while (p && p->data < mink) {
        // Pre points to the precursor
        pre = p;
        p = p->next;
    }
    
    //2. Find the first node whose value is greater than or equal to maxk
    while (p && p->data < maxk) {
        p = p->next;
    }
    
    //3. Modify the pointer of the node to be deleted
    q = pre->next;
    pre->next = p;
    
    // Release all nodes between q and p
    while (q != p) {
        temp = q->next;
        free(q);
        q = temp;
    }
}
Copy the code

Time complexity:

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

Test verification:

void test4() {
    printf("Test deleteMinMax: \n");
    KStatus iStatus;
    LinkList La.Lb.L;
    initList(&La);
    initList(&Lb);
    
    printf(Topic 4: "* * * * * * * * * * * * * * \ n");
    initList(&L);
    for(int j = 10; j>=0; j-=2)
    {
        iStatus = insertElement(&L.1, j);
    }
    printf("L list: \ n");
    traverseList(L);

    deleteMinMax(&L.4.10);
    printf("Delete linked list between mink and maxk :\n");
    traverseList(L);
}

Copy the code

Output result:

Delete mink from maxk: 0 2 10. Delete mink from maxk: 0 2 10Copy the code

1.1.5 Circular shift left

Title 5: Suppose n(n>1) integers are stored in a one-dimensional array R. Try to design an algorithm that is as efficient as possible in both space and time. The sequence saved in R is cyclically shifted to the left by P positions (0< P

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}

Let’s analyze and solve the problem:

Analyze the key words of the topic and find out the details:
Analyze the problem and list the solution ideas:

Algorithm idea:

First, invert n data in situ 9,8,7,6,5,4,3,2,1,0;

Disassemble n data into [9,8,7,6,5,4,3] [2,1,0]

The first n-P data and the last P data were inverted in situ respectively. ,4,5,6,7,8,9 [3] [0]

Problem solving and code implementation:

// Invert the data in array R in place
void reverseList(int *pre, int left, int right) {
    // I equals left,j equals right;
    int i = left, j = right;
    int temp;
    
    // Swap pre[I] and pre[j] values
    while (i < j) {
        / / interaction
        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) {
    // Loop the data in array pre of length N to the left by p positions
    if (p > 0 && p < n) {
        //1. Invert all the elements in the array
        reverseList(pre, 0, n-1);
        //2. Invert the first n-p data
        reverseList(pre, 0, n-p-1);
        //3. Invert the last P data
        reverseList(pre, n-p, n-1); }}Copy the code

Time complexity:

Complexity analysis: time complexity: O(n); Time complexity :O(1);

Test verification:

void test5() {
    printf("Test deleteMinMax: \n");
    LinkList La.Lb;
    initList(&La);
    initList(&Lb);
    
    printf(Title 5: "* * * * * * * * * * * * * * \ n");
    int pre[10] = {0.1.2.3.4.5.6.7.8.9};
    leftShift(pre, 10.3);
    for (int i=0; i < 10; i++) {
        printf("%d ",pre[i]);
    }
    printf("\n");
}

Copy the code

Output result:

Test deleteMinMax :****** Question 5:******** 3 4 5 6 7 8 9 0 1 2Copy the code

1.1.6 Find the main element

Title 6: Given A sequence of integers A= (A0, A1,a2… ,an-1), where (0<=ai <= n), (0<= I <= n). If any ap1 = ap2 =… = apm = x, and m>n/2(0<= PK

Let’s analyze and solve the problem:

Analyze the problem firstThe keyword, find out the details:

The primary element is the element that occurs more than half the time in the 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.

Analyze the problem and list the solution ideas:

Algorithm idea:

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;

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;

Problem solving and code implementation:

// Find the main element of the integer sequence A;
int findMainElement(int *A, int n) {
    //count is used to count things
    int count = 1;
    //key is used to hold the candidate primary element, the initial A[0]
    int key = A[0];
    
    //(1) scan array, select candidate primary element
    for (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 {
            //(1) A[I] is not A candidate primary element, and the count is reduced by 1;
            if (count > 0) {
                count-; }else {
                //(4) If count is 0, replace the candidate primary element and count again
                key = A[i];
                count = 1; }}}If count > 0, there are candidate elements. If count > 0, there are candidate elements. Otherwise, there are no candidate elements.
    if (count > 0) {
        //(5) Count the actual occurrence times of candidate elements
        for (int i = count = 0; i < n; i++) {
            if(A[i] == key) count++;
        }
    }
    //(6) Determine whether the candidate element meets the main element condition, that is, the number of occurrences is greater than half of the array length
    if (count > n/2) return key;
    
    //(7) Main element not found, return -1
    return -1;
}
Copy the code

Time complexity:

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

Test verification:

void test6() {
    printf("Test findMainElement: \n");
    printf(Topic 6: "* * * * * * * * * * * * * * \ n");
    int  A[] = {0.5.5.3.5.7.5.5};
    int  B[] = {0.5.5.3.5.1.5.7};
    int  C[] = {0.1.2.3.4.5.6.7};

    int value = findMainElement(A.8);
    printf("Array A's main element is: %d\n",value);
    value = findMainElement(B.8);
    printf("Array B with primary elements (-1 means no primary elements): %d\n",value);
    value = findMainElement(C.8);
    printf("Array C with primary elements (-1 means array with no primary elements): %d\n",value);
}
Copy the code

Output result:

Test findMainElement: title 6: * * * * * * * * * * * * * * array is A main element to: five major elements of the array B for the major elements of the array (1 said no) : 1 major elements of the array C for the major elements of the array (1 said no) : 1Copy the code

1.1.7 Preserve the node that appears for the first time

Topic 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 that’s as efficient as possible. For nodes in the linked list whose data absolute values are opposite, only the first node is retained, and the remaining nodes with equal absolute values are deleted. For example, linked list A= {21,-15,15, -7,15}, deleted linked list A= {21,-15,-7}; .

Let’s analyze and solve the problem:

Analyze the problem firstThe keyword, find out the details:

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.

Analyze the problem and list the solution ideas:

Algorithm idea:

Apply for auxiliary array t of size n+1 and assign initial value 0;

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.

Problem solving and code implementation:

// Target: delete nodes with equal absolute values from a single linked list;
void deleteSameNode(LinkList *L, int n) {
    //1. Open the auxiliary array p.
    int *p = malloc(sizeof(int) * n);
    LinkList r = *L;
    
    //2. The initial value of the array element is null
    for (int i = 0; i < n; i++) {
        *(p+1) = 0;
    }
    
    //3. The pointer temp points to the initial node
    LinkList temp = (*L)->next;
    
    //4. Iterate through the list until temp = NULL;
    while (temp) {
        //5. If the absolute value already exists on the node, delete the node
        if (p[abs(temp->data)] == 1) {
            // Delete the node
            //5.1 Temporary pointer r points to temp->next
            r->next = temp->next;
            //5.2 Delete the node pointed to by temp
            free(temp);
            //5.3 temp points to the node next to the deleted node
            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;
            // Continue traversingtemp = temp->next; }}}Copy the code

Time complexity:

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

Test verification:

void test7() {
    printf("Delete nodes with equal absolute values in a single linked list: \n");
    LinkList L;

    / / 21, 15, 15, 7, 15
    printf(Topic 7: "* * * * * * * * * * * * * * \ n");
    initList(&L);
    insertElement(&L.1.21);
    insertElement(&L.1, -15);
    insertElement(&L.1.15);
    insertElement(&L.1, -7);
    insertElement(&L.1.15);

    deleteSameNode(&L.21);
    traverseList(L);
}
Copy the code

Output result:

Delete nodes with equal absolute values from a single linked list :****** Questions 7:******** 15-7 21Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structure and algorithm (4) linked list related interview questions

1. Data structure and algorithm (4) Linked list related interview questions

1.1 Linked list algorithm details

1.1.1 Merge two ordered lists

1.1.2 Find the intersection of two ordered linked lists

Reverse an ordered linked list

1.1.4 Delete certain conditional elements

1.1.5 Circular shift left

1.1.6 Find the main element

1.1.7 Preserve the node that appears for the first time

Data structure and algorithm (4) linked list related interview questions

1. Data structure and algorithm (4) Linked list related interview questions

1.1 Linked list algorithm details

1.1.1 Merge two ordered lists

1.1.2 Find the intersection of two ordered linked lists

Reverse an ordered linked list

1.1.4 Delete certain conditional elements

1.1.5 Circular shift left

1.1.6 Find the main element

1.1.7 Preserve the node that appears for the first time

Related Posts

Alamofire learning

Flutter(XI) – Project construction

01: Alloc&init