This is the 26th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

2. Delete all nodes with value x (no recursion required)

Create a pointer to p and pre, one to the current node and one to the previous node

If the same is encountered, then the node is “crossed”

3. Output the linked list in reverse

The output goes from the inner layer to the outer layer

4. Delete the smallest element in the list

Maintain the minimum pointer and its precursor pointer, iterate over the minimum and delete it

void DeleMin(LinkList &L){
    
    LNode *pre=L,*p=pre->next;
    LNode *minpre=pre,*minp=p;      // Record the minimum value node and its precursor

    while(p ! =NULL) {if(p->data < minpre->data){     // The latter is smaller than the former
            min = p;            // The maintenance min is in the minimum position
            minpre = pre;       // Maintain minPre in the smallest node of the precursor
        }
        p = p->next;        // Stride forward
        pre = pre->next;    // Stride forward
    }
    minpre->next = min->next;    // Delete the minimum value
    free(minp);
    return L;
}
Copy the code

5. The linked list is reversed in place

Keep two Pointers, cur and Pre, in front of cur

ListNode reverseList(ListNode head) {
        ListNode *pre = NULL, *cur = head;
        while(cur ! =NULL) {
            ListNode *t = cur->next;         // save the next pointer to cur
            cur->next = pre;                  / / cur pointing in the direction of the pre
            pre = cur;                        //cur take a step forward
            cur = t;                        // Pre takes a step forward
        }
        return pre;
    }
    
Copy the code

6. Rearrange the linked list into an increasing sequence

Insert into the previous ordered table, using each node traversed by insertion sort

void Sort(LinkList &L){
        LNode *p = L->next;
        LNode *r = p->next;     // Save the successor of p to prevent chain breaking
        LNode *pre;
        p->next = NULL;     // create the first ordered table
        p = r;
 
        while(p ! =NULL){
            r = p->next;
            pre = L;
            while(pre->next ! =NULL && pre->next->data < p->data){
                pre = pre->next;        // Pre goes forward and looks for a precursor to insert p
            }
            p->next = pre->next;    // Insert *p after *prepre->next = p; p = r; }}Copy the code