(Data Structures: Linked List) Move odd items to the back of list

Question

I am supposed to implement a function void moveOddItemsToBack(LinkedList *ll) that moves all odd integers to back of the linked list ll.

It is able to compile and run, however the numbers are not in the right order and I am unsure why :( The code I have written is as shown:

void moveOddItemsToBack(LinkedList *ll)
{
    ListNode *cur = ll-> head;
    int orgsize = ll->size; 
    index =0;   

    //check for empty list
    if (cur == NULL) return;

    //if list not empty, traverse entire list
    while (orgsize > 0){

        //if odd no
        if (cur->item %2 !=0){
        insertNode(ll, ll->size, cur->item);  //insert the odd number into last item on list
        cur = cur -> next;
        removeNode(ll, index); //remove the odd number in the original index
        }

        //if not odd no, just continue traversing list
        else cur = cur -> next;

        orgsize--;   //original size decreases every while loop so as to inspect the original nodes' integers and not the integers i added to the back of list
        index++;  //index increases by 1 everytime i move my cur ptr to the next node
    }
}

Main code given:

#include <stdlib.h>

//////////////////////////////////////////////////////////////////////////////////

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;         // You should not change the definition of ListNode

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;           // You should not change the definition of LinkedList


//////////////////////// function prototypes /////////////////////////////////////

// You should not change the prototype of this function
void moveOddItemsToBack(LinkedList *ll);

void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);

//////////////////////////// main() //////////////////////////////////////////////

int main()
{
    LinkedList ll;
    int c, i, j;
    c = 1;
    //Initialize the linked list 1 as an empty linked list
    ll.head = NULL;
    ll.size = 0;


    printf("1: Insert an integer to the linked list:\n");
    printf("2: Move all odd integers to the back of the linked list:\n");
    printf("0: Quit:\n");

    while (c != 0)
    {
        printf("Please input your choice(1/2/0): ");
        scanf("%d", &c);

        switch (c)
        {
        case 1:
            printf("Input an integer that you want to add to the linked list: ");
            scanf("%d", &i);
            j = insertNode(&ll, ll.size, i);
            printf("The resulting linked list is: ");
            printList(&ll);
            break;
        case 2:
            moveOddItemsToBack(&ll); // You need to code this function
            printf("The resulting linked list after moving odd integers to the back of the linked list is: ");
            printList(&ll);
            removeAllItems(&ll);
            break;
        case 0:
            removeAllItems(&ll);
            break;
        default:
            printf("Choice unknown;\n");
            break;
        }
    }
    return 0;
}

Function removeNode given:

    ListNode *pre, *cur;

    // Highest index we can remove is size-1
    if (ll == NULL || index < 0 || index >= ll->size)
        return -1;

    // If removing first node, need to update head pointer
    if (index == 0){
        cur = ll->head->next;
        free(ll->head);
        ll->head = cur;
        ll->size--;

        return 0;
    }

    // Find the nodes before and after the target position
    // Free the target node and reconnect the links
    if ((pre = findNode(ll, index - 1)) != NULL){

        if (pre->next == NULL)
            return -1;

        cur = pre->next;
        pre->next = cur->next;
        free(cur);
        ll->size--;
        return 0;
    }

    return -1;
}

Function insertNode given:

int insertNode(LinkedList *ll, int index, int value){

    ListNode *pre, *cur;

    if (ll == NULL || index < 0 || index > ll->size)
        return -1;

    // If empty list or inserting first node, need to update head pointer
    if (ll->head == NULL || index == 0){
        cur = ll->head;
        ll->head = malloc(sizeof(ListNode));
        ll->head->item = value;
        ll->head->next = cur;
        ll->size++;
        return 0;
    }


    // Find the nodes before and at the target position
    // Create a new node and reconnect the links
    if ((pre = findNode(ll, index - 1)) != NULL){
        cur = pre->next;
        pre->next = malloc(sizeof(ListNode));
        pre->next->item = value;
        pre->next->next = cur;
        ll->size++;
        return 0;
    }

    return -1;
}

Answer 1

No need to count; just perform one pass over the linked list:

---

#include <stdio.h>

typedef struct zzz {
        struct zzz *next;
        int item;
        } LinkedList;

LinkedList items[] =
{ { items+1, 0 }
, { items+2, 1 }
, { items+3, 2 }
, { items+4, 3 }
, { items+5, 4 }
, { NULL, 5 }
        };

void moveOddItemsToBack(LinkedList **ll);
void moveOddItemsToBack(LinkedList **ll)
{

LinkedList *odds=NULL, **pp = &odds;

for ( ; *ll;    ) {
        LinkedList *this;
        this = *ll;
                /* leave this one; it is even */
        if ( !( this->item %2) ) {
                ll = &this->next;
                continue;
                }
                /* Skip over it (cut it out of the original list)
                ** , and append to the list of odds
                */
        *ll = this->next;
        *pp = this;
        pp = &this->next;
        }

        /* terminate odds-chain, and append to the tail of evens */
*pp = NULL;
*ll = odds;
}

int main(void)
{
LinkedList *root;
root = items;

moveOddItemsToBack(&root);

for (   ; root; root = root->next) {
        printf("%d\n", root->item);
        }
return 0;
}