Deleting Node from Singly Linked List C

Question

I am checking the parity of the length of a singly linked list:

• if it's odd, I have to delete the first node;
• if it's even, I have to delete the last node.

I am able to figure out the parity but can't delete the relevant nodes.

Given that I also have to use the signature void sil(struct node **head), what should I change and add to my code?

// C program to check length
// of a given linklist 
#include<stdio.h> 
#include<stdlib.h>

// Defining structure 
struct Node 
{ 
    int data; 
    struct Node* next; 
}; 
  
// Function to check the length of linklist 
int LinkedListLength(struct Node* head) 
{ 
    while (head && head->next) 
    { 
        head = head->next->next; 
    } 
    if (!head) 
        return 0; 
    return 1; 
} 
      
// Push function 
void push(struct Node** head, int info) 
{ 
    // Allocating node 
    struct Node* node = (struct Node*) malloc(sizeof(struct Node)); 
      
    // Info into node 
    node->data = info; 
      
    // Next of new node to head 
    node->next = (*head); 
  
    // head points to new node 
    (*head) = node; 
} 
  
// Driver function 
int main(void) 
{ 
    struct Node* head = NULL; 
      
    // Adding elements to Linked List 
    push(&head, 4); 
    push(&head, 5); 
    push(&head, 7); 
    push(&head, 2); 
    push(&head, 9); 
    push(&head, 6); 
    push(&head, 1); 
    push(&head, 2); 
    push(&head, 0); 
    push(&head, 5); 
    push(&head, 5);
    int check = LinkedListLength(head); 
      
    // Checking for length of 
    // linklist 
    if(check == 0) 
    { 
        printf("Even\n"); 
    } 
    else
    { 
        printf("Odd\n"); 
    } 

   return 0; 
} 

Answer 1

"I am checking if the singly linked list is odd or even. If it's odd I have to delete first node and if it's even I have to delete last node. I did the part where I found it's odd or even. But I can't delete nodes. I'll be really happy if you can help. Also I have to use this parameter " void sil(struct node **head) " What should I change and add to my code?"

    #include<stdio.h> 
    #include<stdlib.h>
    
    struct node{ 
        int data; 
        struct node *next; 
    }; 

    void push(struct node** head, int info) { 
        struct node *newN = (struct node *) malloc(sizeof(struct node)); 
          
        newN->data = info; 
        newN->next = *head; 

        *head= newN; 
    } 
    
    void sil(struct node **head){
           if (*head==NULL) return;

           struct node *ptail=NULL;
           struct node *tail=*head;
           int i;

           for (i=1; tail->next!=NULL; ptail=tail, i++, tail=tail->next);

           if (i%2){
                tail=*head;
                *head=(*head)->next;
           }else{
                ptail->next=NULL;
           }

           free(tail);
    }

    int main(void){ 
        struct node *head = NULL; 
         
        push(&head, 4); 
        push(&head, 5); 
        push(&head, 7); 
        push(&head, 2); 
        push(&head, 9); 
        push(&head, 6); 
        push(&head, 1); 
        push(&head, 2); 
        push(&head, 0); 
        push(&head, 5); 
        push(&head, 5);

        sil(&head);

       return 0; 
    } 

Try it.

Answer 2

typedef struct Node Node;

You can do that relatively easily with a simple function that takes the address of your list and the parity value as parameters, e.g.

/** delete 1st or last node from list given parity, 
 *  parity odd, delete 1st node, otherwise delete last
 */
void del_first_last_node (Node **head, int parity)
{
    Node **ppn = head;          /* pointer to pointer */
    Node *pn = *head;           /* pointer to node */

    if (parity & 1) {           /* is parity odd delete first node */
        *ppn = pn->next;        /* set node at current address to next */
        free (pn);
        return;
    }
    
    for (; pn; ppn = &pn->next, pn = pn->next) {    /* loop to end */
        if (pn->next == NULL) { /* if next pointer NULL */
            *ppn = pn->next;    /* set node at current address to next */
            free (pn);
            break;
        }
    }
}

Above, parity is checked for odd, and if so, the first node is deleted (and properly freed). If the parity is even, you loop to the end of the list and delete the last node (again freeing the deleted node)

Iterating with both the address of the node and a pointer to node means there is no need to keep track of the prior node or any special cases. You are simply replacing the node at the current address with the next in the list. In the case of the first node, you just replace the node at the current head address with the next node (and since you also maintain a pointer to the node which is unchanged, you use that to free the original node) For the last node, you are just replacing its contents with NULL. See Linus on Understanding Pointers

Answer 3

the idea behind deleting a node is in general the same:

1. Create temp node that points to the node you want to delete in your structure.

2. If you want to delete the head, you can first point to the head with your temp node and then set your head to point to the item next to it. It should look something like this: node->head = node->head->next; and then of course free your temp pointer.

3. If you want to delete the tail, there are several cases to be covered. If you don't use a sentinel node , you have to traverse your list in a way that it will not destroy or corrupt the original one. The code for that should look like this:

   int deleteTail(list_t* list){
   
      int toReturn;
      //declare a temp pointer to the head of your list
      node_t* temp = list->head;
      //here you found the last node and have it in a temp pointer.
      while(temp->next != NULL) temp=temp->next;
      //get the value you want to return
      toReturn = temp->data;
      //free the last element
      free(temp);
      return toReturn;
   
   }