Implementation of data structures in C

Data Structures in C

## Singly Linked List
- new node
- size
- insert at beginning
- insert at end
- insert at position
- delete at beginning
- delete at end
- delete at position
- print list
- compare two lists
- detect loop
- reverse
- concat two lists

singly_linked_list.c

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct Node {
    int val;
    struct Node* next;
};

struct Node* newNode(int val) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->val = val;
    node->next = NULL;
    
    return node;
}

int size(struct Node* head) {
    int s = 0;
    struct Node* t = head;
    while(t) {
        t = t->next;
        s++;
    }
    return s;
}

void insertNode(struct Node** head_ptr, int val) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->val = val;
    node->next = NULL;
    
    if (*head_ptr == NULL) {
        (*head_ptr) = node;
    } else {
        (*head_ptr)->next = node;
    }
}

void insertAtBeginning(struct Node** head_ref, int new_data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->val = new_data;
  new_node->next = (*head_ref);

  (*head_ref) = new_node;
}

void insertAtPos(struct Node** head_ref, int new_data, int pos) {
    struct Node *node = (struct Node*) malloc(sizeof(struct Node));
    node->val = new_data;

    if (pos == 0) {
        node->next = (*head_ref);
        (*head_ref) = node;
        return;
    }

    struct Node *cur = (*head_ref);

    for(int i=0; i < pos-1; i++) {
      cur = cur->next;
    }
    node->next = cur->next;
    cur->next = node;
}

void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->val = new_data;
    new_node->next = NULL;
    
    if ((*head_ref) == NULL) {
        (*head_ref) = new_node;
        return;
    }
    
    struct Node* tail = (*head_ref);
    while(tail && tail->next) tail = tail->next;

    tail->next = new_node;
}

void deleteAtBeginning(struct Node** head_ref) {
    struct Node* new_head = (*head_ref)->next;

    free(*head_ref);

    (*head_ref) = new_head;
}

void deleteAtEnd(struct Node** head_ref) {
    struct Node* tail = (*head_ref);
    while(tail && tail->next && tail->next->next) tail = tail->next;
    
    free(tail->next);

    tail->next = NULL;
}

void deleteAtPos(struct Node** head_ref, int pos) {
    
    if ((*head_ref) == NULL) return;

    if (pos == 0) {
        free(*head_ref);
        return;
    }

    struct Node *cur = (*head_ref);

    for(int i=0; i < pos-1; i++) {
      cur = cur->next;
    }
    
    struct Node* tmp = cur->next;
    cur->next = cur->next->next;
    
    free(tmp);
}

void printList(struct Node* head) {
    if (head == NULL) return;
    if (head->next)
        printf("%d->", head->val);
    else
        printf("%d", head->val);
    printList(head->next);
}

int compare(struct Node* headA, struct Node* headB) {
    while (headA != NULL && headB != NULL) {
        if (headA->val == headB->val) {
            headA = headA->next;
            headB = headB->next;
        } else {
            return 0;
        }
    }
    
    if (headA == NULL && headB == NULL)
        return 1;
    else
        return 0;
}

int find_loop(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;
    
    while(slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) return 1;
    }

    return 0;
}

void reverse(struct Node** head_ref) {    
    struct Node* prev = NULL;
    struct Node* cur = head;
    struct Node* next = NULL;
    
    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        
        prev = cur;
        cur = next;
    }
    
    (*head_ref) = prev;
}


// TODO: convert
LinkedListNode* concat(LinkedListNode* node1, LinkedListNode* node2) {   
    if (node2 == NULL) return node1;
    
    if (node1 == NULL) return node2;
    
    int size1 = 0, size2 = 0;
    
    LinkedListNode* t = node1;
    while(t) {
        t = t->next; size1++;
    }
    
    t = node2;
    while(t) {
        t = t->next; size2++;
    }
    
    if (size1 < size2) {
        LinkedListNode* tail1 = node1;
        while (tail1 && tail1->next) tail1 = tail1->next;

        tail1->next = node2;

        return node1;
    } else {
        LinkedListNode* tail2 = node2;
        while (tail2 && tail2->next) tail2 = tail2->next;

        tail2->next = node1;

        return node2;
    }
}