Pointers in c: A function that removes every second element of a linked list

Question

I want to write a function that gets a pointer to the title of a linked list and removes every second member from the list. A list is a related element of an element of type:

typedef struct element{ int num; struct element* next; }element; 

I am new to all of these arithmetic pointers, so I'm not sure if I am writing them correctly:

  void deletdscnds(element* head) { element* curr; head=head->next; //Skipping the dummy head// while (head!=NULL) { if (head->next==NULL) return; else { curr=head; head=head->next->next; //worst case I'll reach NULL and not a next of a null// curr->next=head; } } } 

I constantly changed it, as I continued to find errors. Could you point out possible errors?

Answer 1

The algorithm is much simpler if you think about your linked list in terms of node pairs. Each iteration of your loop should process two nodes - head and head->next , and after the exit, head is equal to head->next->next . It is also important to remember to remove the middle node if you cut it out of the list, otherwise you will see a memory leak.

 while (head && head->next) { // Store a pointer to the item we're about to cut out element *tmp = head->next; // Skip the item we're cutting out head->next = head->next->next; // Prepare the head for the next iteration head = head->next; // Free the item that no longer in the list free(tmp); } 

Answer 2

It can be very simple to visualize this problem in recursive terms, for example:

 // outside code calls this function; the other functions are considered private void deletdscnds(element* head) { delete_odd(head); } // for odd-numbered nodes; this won't delete the current node void delete_odd(element* node) { if (node == NULL) return; // stop at the end of the list // point this node to the node two after, if such a node exists node->next = delete_even(node->next); } // for even-numbered nodes; this WILL delete the current node void delete_even(element* node) { if (node == NULL) return NULL; // stop at the end of the list // get the next node before you free the current one, so you avoid // accessing memory that has already been freed element* next = node->next; // free the current node, that it not needed anymore free(node); // repeat the process beginning with the next node delete_odd(next); // since the current node is now deleted, the previous node needs // to know what the next node is so it can link up with it return next; } 

For me, at least, it helps to clarify what needs to be done at every step.

I would not recommend using this method, because in C recursive algorithms can take up a lot of RAM and cause a stack overflow with compilers that do not optimize them. Rather, the dasblinkenlight response contains code that you really should use.