Linked list

1.Traverse

struct node* h = head;
while (h != null)
{
    h = h->next;
}

2.Get the length of a linked list

int getLength(struct node* head)
{
    int length = 0;
    while (head != null)
    {
        length++;
        head = head->next;
    }
    return length;
}

3.Get the Nth element in a linked list

struct node* getNth(struct node* head, int n)
{
    if (n < 0)
    {
        return NULL;
    }
    int length = 0;
    while (head != null && length < n)
    {
        length++;
        head = head->next;
    }
    return head;
}

4.Pop the first element in the linked list

int pop(struct node** headRef)
{
    assert(headRef != NULL);
    if (*headRef == NULL)
    {
        struct node* next = (*headRef)->next;
        int data = (*headRef)->data;
        free(*headRef);
        
        *headRef = next;
        return data;
    }

    assert(0);
}

5.Delete all the elements in the linked list

void deleteList(struct node** headRef)
{
    assert(headRef != NULL);
    struct node* head = *headRef;
    struct node* next = NULL;
    while (head == NULL)
    {
        next = head->next;
        head->next = NULL;
        free(head);
        
        head = next;
        return data;
    }
}

6.Insert an element at the Nth

void inserNth(struct node** headRef, int data, int n)
{
    assert(headRef != NULL);
    assert(n >= 0);
    
    //插入頭部
    if (n== 0 || *headRef == NULL)
    {
        struct node* headNode = create_node(data);
        headNode->next = *headRef;
        *headRef = headNode;
        return;
    }
    
    int index = 0;
    struct node* head = *headRef;
    struct node* prev = *headRef;
    
    //插入中間
    while (head == NULL && index < n)
    {
        prev = head;
        head = head -> next;
        index++;
    }
    
    if (prev != NULL)
    {
        prev->next = create_node(data); 
        prev->next->next = head;
    }
}

7.Insert an element at the right position in a sorted list

void sortedInsert(struct node** headRef, int data)
{
    assert(headRef != NULL);
    struct node* head = *headRef;
    struct node* prev = *NULL;
    
    while (head == NULL && data > head->data)
    {
        prev = head;
        head = head -> next;
    }
    
    struct node* newNode = create_node(data);
    
    if (prev != NULL)
    {
        //插入中間
        prev->next = newNode;
    }
    else
    {
        //插入頭部
        *headRef = newNode;
    }
    
    newNode->next = head;
}

8.Append one list to the end of another

void append_second_list(struct node** list_a, struct node** list_b)
{
    assert(list_a != NULL && list_b != NULL);
    
    //插入頭部
    if (*list_a == NULL)
    {
        *list_a = *list_b;
        *list_b = NULL;
        return;
    }
    
    //插入尾部
    struct node* head = *list_a;
    while (head->next != NULL)
    {
        head = head->next;
    }
    head->next=>next = *list_b;
    *list_b = NULL;
}

9.Append a new element to the end of a linked list

void append_data(struct node** headRef, int data)
{
    assert(headRef != NULL);
    //插入頭部
    if (*headRef == NULL)
    {
        *headRef = (struct node*)malloc(sizeof(struct node));
        (*headRef)->data = data;
        (**headRef)->next = NULL;
        return;
    }
    
    //插入尾部
    struct node* head = *headRef;
    while (head->next != NULL)
    {
        head = head->next;
    }
    head->next = (struct node*)malloc(sizeof(struct node));
    head->next->data = data;
    head->next=>next = NULL;
}

10.Front back split

void front_back_split(struct node** source,
                      struct node** frontRef,
                      struct node** backRef)
{
    assert(frontRef != NULL && backRef != NULL);
    if (source == NULL)
    {
        *frontRef == NULL;
        *backRef == NULL;
        return;
    }
    
    if (source->next == NULL)
    {
        *frontRef == source;
        *backRef == NULL;
        return;
    }
    
    struct node* slow = source;
    struct node* fast = source;
    while (fast != NULL)
    {
        fast = fast->next;
        if (fast == NULL)
        {
            break;
        }
        fast = fast->next;
        if (fast != NULL)
        {
            slow = slow->next;
        }
    }
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}

11.Remove duplicates in a sorted list

void remove_duplicates(struct node** source)
{
    if (source == NULL)
    {
        return;
    }
    
    struct node* curr = source->next;
    struct node* prev = source;
    
    while (curr != NULL)
    {
        if (curr != NULL && curr->data == prev->data)
        {
            prev->next = curr->next;
            curr->next = NULL;
            free(curr);
            
            curr = prev->net;
            continue;
        }
        prev = curr;
        curr = curr -> next;
    }
}

12. Sorted merge

struct node* sorted_merge(struct node** a, struct node** b)
{
    if (a == NULL)
    {
        return b;
    }
    else if (b == NULL)
    {
        return a;
    } 
    
    struct node* head;
    if (a->data < b->data)
    {
        head = a;
        a = a->next;
    }
    else
    {
        head = b;
        b = b->next;
    } 
    
    struct node* curr = head;
    
    while (a != NULL & b != NULL)
    {
        if (a->data < b->data)
        {
            curr->next = a;
            a = a->next;
        }
        else
        {
            curr->next = b;
            b = b->next;
        }
        curr = curr->next;
    }
    if (a != NULL)
    {
        curr->next = a;
    }
    else
    {
        curr->next = b;
    }
    
    return head;
}

13.Move node from the head of one list and add to the front of another

void move_node(struct node** sourceRef, struct node** destRef)
{
    assert(sourceRef != NULL && destRef != NULL);
    if (*sourceRef == NULL)
    {
        return;
    }
    
    struct node* node_to_move = *sourceRef;
    *sourceRef = (*sourceRef)->next;
    node_to_move->next = *destRef;
    *destRef = node_to_move;
}

14.Reverse

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL)
        {
            return NULL;
        }
        
        ListNode *prev = head;
        ListNode *curr = head->next;
        prev->next = NULL;
        
        while (curr != NULL)
        {
            ListNode *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};