How to move certain elements from linked list at the end of that list?

Question

Today i was trying to make a program that would enter 15 random values (from 100 to 120) into linked list. That part works like a charm. Then I went to find the max and the min values from that list, and find the average.

I want to move all values greater than average to the end of that list which I tried to realise using function prebaci. Function unos puts all elements into the list, and function unosK puts all elements at the end of the list. Program goes into infinite loop, and I don't know why. Can you help me to move all values greater than average (107) to the end of the list? My CODE:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct lista* Pozicija;
struct lista {
    int el;
    Pozicija next;
};

void unos(Pozicija P, int el);//input front
void ispis(Pozicija P);//print 
int mini(Pozicija P);//find min
int maxi(Pozicija P);//find max
void prebaci(Pozicija P,int x);//function for transfering at the end
void unosK(Pozicija P,int x);//input end

int main() {
    srand(time(0));
    struct lista L;
    L.next = NULL;
    int min,max, i,j;
    int prvi[21], drugi[15];
    int avg;

    
    for (i = 0;i < 21;i++) {
        prvi[i] = i + 100;
        printf("%d ", prvi[i]);
    }
    for (i = 0;i < 15;i++) {
        int temp = prvi[i];
        int random = rand() % 15;

        prvi[i] = prvi[random];
        prvi[random] = temp;
    }
    printf("\n\n");
    for (i = 0;i < 15;i++) {
        //printf("%d ",prvi[i]);
        unos(&L, prvi[i]);
    }

    printf("Ispis\n");
    ispis(L.next);

    printf("\n\n");
    min = mini(L.next);
    printf("Minqi:%d\n", min);

    printf("\n\n");
    max = maxi(L.next);
    printf("Miaxi:%d\n", max);

    printf("\n\n");
    avg = (min + max) / 2;
    printf("avg:%d\n", avg);

    printf("\n\n");
    printf("Prebacaj:\n");
    prebaci(&L, avg);
    ispis(L.next);

}
void unos(Pozicija P, int el) {
    Pozicija q;
    q = (Pozicija)malloc(sizeof(struct lista));

    q->el = el;
    q->next = P->next;
    P->next = q;
}
void ispis(Pozicija P) {
    while (P != NULL) {
        printf("%d ", P->el);
        P = P->next;
    }
}
int mini(Pozicija P) {
    int min;
    min = INT_MAX;

    while (P != NULL) {
        if (min > P->el) {
            min = P->el;
        }
        P = P->next;
    }
    return min;
}
int maxi(Pozicija P) {
    int max;
    max = INT_MIN;

    while (P != NULL) {
        if (max< P->el) {
            max = P->el;
        }
        P = P->next;
    }
    return max;
}
void prebaci(Pozicija P,int x) {
    P = P->next;
    Pozicija t;
    t = P;
    while (t != NULL) {
        if (t->el > x)
        {
            unosK(P, t->el);
            t = t->next;
        }
        else if (t->el <= x) {
            unos(P, t->el);
            t = t->next;
        }
        
    }

}
void unosK(Pozicija P,int x) {
    Pozicija q=NULL;
    q = (Pozicija)malloc(sizeof(struct lista));
    q->el = x;

    while (P->next != NULL)
            P = P->next;

    
    q->next = P->next;
    P->next = q;

}

Answer 1

Here is a working, drop-in replacement for the original prebaci function. It still has the dummy node at the start of the list, but does not allocate any new elements.

Rather than calling unos and unosK which allocate new elements, it manipulates the pointers in the original list to move the elements greater than the average value to the end of the list.

It first moves the greater than average elements from the original list onto a new, initially empty list (q), and then links the last element of the original list to the first element of the new list so that all the greater than average elements are now at the end of the original list.

The new list (q) has been implemented as a pointer instead of a dummy node.

The function makes use of pointers to pointers (pp and pq) to manipulate the links in the original list and the new list.

void prebaci(Pozicija P,int x) {
    Pozicija *pp = &P->next; /* pointer to link in original list */
    Pozicija q = NULL; /* new list for elements greater than average */
    Pozicija *pq = &q; /* pointer to end link of new list */
    while (*pp != NULL) {
        if ((*pp)->el > x) {
            /* move element from original list to end of new list */
            *pq = *pp;  /* end of new list points to moved element */
            *pp = (*pp)->next; /* remove element from original list */
            pq = &(*pq)->next; /* update pointer to end link of new list */
        }
        else {
            /* do not move this element */
            pp = &(*pp)->next; /* advance to next link in original list */
        }
    }
    *pq = NULL; /* terminate the new list */
    *pp = q; /* append the new list to the end of the original list */
}